当前位置：首页 > news >正文

安居客房产官方网站福州网站改版

news 2025/9/17 9:08:10

安居客房产官方网站,福州网站改版,电商app排行榜,做冲压件加工有什么好网站目录堆的结构类型定义最大堆的创建堆的插入堆的插入的三种情况代码实现哨兵元素堆的结构类型定义 #define ElementType int typedef struct HNode* Heap; /* 堆的类型定义 */ struct HNode {ElementType* Data; /* 存储元素的数组 */int Size; /* 堆中…

堆的结构类型定义

最大堆的创建

堆的插入

堆的插入的三种情况

代码实现

哨兵元素

堆的结构类型定义

#define ElementType int
typedef struct HNode* Heap; /* 堆的类型定义 */
struct HNode 
{ElementType* Data; /* 存储元素的数组 */int Size;          /* 堆中当前元素个数 */int Capacity;      /* 堆的最大容量 */
};

HNode中的两个成员变量：

一个ElementType类型的指针Data，用于存储堆中的元素；

一个int类型的Size，用于表示堆中当前的元素个数；

还有一个int类型的Capacity，用于表示堆的最大容量。

最大堆的创建

typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */#define MAXDATA 1000  /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */MaxHeap CreateHeap(int MaxSize)
{ /* 创建容量为MaxSize的空的最大堆 */MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));H->Data = (ElementType*)malloc((MaxSize + 1) * sizeof(ElementType));H->Size = 0;H->Capacity = MaxSize;H->Data[0] = MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/return H;
}

参数MaxSize表示创建的最大堆的最大容量。

首先，使用malloc申请了HNode结构体类型的内存空间。

接下来，使用malloc申请了(MaxSize+1)个ElementType类型的元素的内存空间，并将申请的指针赋值给H->Data，这个Data数组就是用来存储最大堆中的元素的。

而其中，要申请的内存空间不是MaxSize而是MaxSize+1，是因为：

堆的下标是从1开始的，而不是从0开始的。这样设计的原因是为了方便定位节点和父子节点之间的关系。

下标为0的元素我们定义为“哨兵”，其值应该大于堆中所有可能元素的值，哨兵的作用在后面会详细阐述。

堆的插入

堆的插入的三种情况

代码实现

bool Insert( MaxHeap H, ElementType X )
{ /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */int i;if ( IsFull(H) ) { printf("最大堆已满");return false;}i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */for ( ; H->Data[i/2] < X; i/=2 )H->Data[i] = H->Data[i/2]; /* 上滤X */H->Data[i] = X; /* 将X插入 */return true;
}

首先判断最大堆是否已满，如果已满则返回false。

如果不满，则将堆的大小加1，i指向插入后堆中的最后一个元素的位置。

然后从i开始向上遍历，如果父结点的值小于X，则将父结点的值下移，直到找到X的插入位置。

这其中有一个关键知识点：

H->Data[0]是哨兵元素，它不小于堆中的最大元素，控制循环结束。