堆的结构类型定义
#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]是哨兵元素，它不小于堆中的最大元素，控制循环结束。
哨兵元素
假定没有哨兵元素或哨兵元素的值为0，而最大堆中的第一个元素是里面的最大值。
那我们看个例子：(关注数组下标i的变化)
插入操作的时间复杂度为： T(N)=O(log2N)
end
