摘要：
堆优先级队列是一个特殊的队列。元素的取出顺序取决于元素的优先级（关键字）大小。元素取出并放入队列的顺序如下：搜索最大值（最小值）、删除（最大值）数组：链表：有序数组：有序链表：二进制搜索树=H-˃Size表示子节点不是最后一个节点。此父节点也有一个右节点。19//如果右节点的值大于左节点的值，则子节点++；20if（孩子！
堆（优先队列）priority queue
特殊的队列，取出元素的顺序是依照元素的优先权（关键字）大小，而出元素进入队列的先后顺序
操作：查找最大值（最小值），删除（最大值）
数组：
链表：
有序数组：
有序链表：
采用二叉搜索树？ NO
采用完全二叉树 YES
堆的连个特性
结构性：用数组表示的完全二叉树：
有序性：任一结点的关键字是其字树所有结点的最大值（或最小值）
最大堆（MaxHeap）也称大顶堆：最大值
最小堆（MinHeap）也称“小顶堆”：最小值
从根节点到任意结点路径上结点序列的有序性
操作：插入任意一个元素，删除最 大值元素
最大堆的删除：取出根节点（最大值）元素，同时删除堆的一个结点
最大堆的建立：将已存在的N个元素按最大堆的要求存放在一个以为数组中
1 #include <stdio.h>
2 #include <stdlib.h>
3 //最大堆
4
5 #define MaxData 1000 //哨兵，该值应该根据具体情况定义为大于堆中所有可能元素的值
6
7 typedef int ElementType;
8
9 typedef struct HeapNode * MaxHeap;
10 struct HeapNode {
11 int Capacity; //堆的最大容量
12 int Size; //堆中当前元素个数
13 ElementType *Data; //用于存储元素的数组
14 };建一个空的最大堆：
1 //建立一个空的最大堆
2 MaxHeap InitHeap(int maxsize)
3 {
4 MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapNode));
5 H->Data = (ElementType*)malloc(sizeof(struct HeapNode) * (maxsize + 1)); //堆中的元素是从下标为1开始存储的，但是为了保证这个堆能存下maxsize个元素，所以要分配maxsize + 1个内存单元
6 H->Capacity = maxsize;
7 H->Size = 0;
8 H->Data[0] = MaxData; //将0下标的单元存储哨兵
9 for (int i = 1; i < maxsize + 1; i++)
10 H->Data[i] = 0;
11 return H;
12 }判断堆是否已满或是否为空：
1 int IsEmpty(MaxHeap H)
2 {
3 return H->Size == 0;
4 }
5
6 //判断堆是否已满
7 int IsFull(MaxHeap H)
8 {
9 return H->Size == H->Capacity;
10 }插入一个元素：
1 //最大堆中插入一个元素
2 void Insert(MaxHeap H, ElementType item)
3 {
4 int i;
5 if (IsFull(H))
6 {
7 printf("The heap is full
");
8 return;
9 }
10 i = ++H->Size; //i为插入后堆中最后一个元素的位置
11 for (; H->Data[i / 2] < item; i /= 2)
12 H->Data[i] = H->Data[i / 2]; //循环退出时，父节点的数据已经大于item， item已经找到了正确的位置
13 H->Data[i] = item; //将item赋给正确的下标单元
14 }删除一个元素：
1 ElementType Delete(MaxHeap H)
2 {
3 ElementType temp, Max;
4 int parent = 1, child;
5 if (IsEmpty(H))
6 {
7 printf("The heap is empty!
");
8 return 0;
9 }
10 Max = H->Data[1]; //现将最大值即根节点的值记录下来
11 temp = H->Data[H->Size--]; //用最后的结点元素暂时代替根节点的数据，然后将堆的数据大小减1
12
13 //如果2 * parent > 0，那么说明parent已经是根节点了
14 for (; 2 * parent <= H->Size; parent = child)
15 {
16 child = 2 * parent;
17
18 //如果Child != H->Size说明child不是最后一个结点，该parent结点还有右节点，
19 //并且如果右节点的值大于左结点，那么child++;
20 if (child != H->Size && (H->Data[child + 1] < H->Data[child]))
21 child++; //child指向左右子节点的较大者
22 if (temp > H->Data[child]) break; //如果孩子结点已经小于temp了， 说明找到了合适的位置
23 else
24 H->Data[parent] = H->Data[child];
25 }
26 H->Data[parent] = temp;
27 return Max;
28 }最大堆的建立：
1.第一步，将N个元素按输入顺序存入二叉树中，这一步需要求满足完全二叉树的结构特性，而不管其有序性
2.从最后一个右孩子的结点开始调整，做类似删除元素时的下滤操作，逐个结点调整，直至根节点
1 //创建一个最大堆
2 MaxHeap CreateMaxHeap()
3 {
4 int dt, i = 0, j;
5 int parent, child;
6 ElementType X;
7 MaxHeap H = InitHeap(20); //先创建一个空的最大堆，然后往里面填充元素
8 while (scanf_s("%d", &dt) != EOF)
9 {
10 H->Data[i + 1] = dt;
11 i++;
12 H->Size++;
13 }
14 for (j = i / 2; j >= 1; j--) //从i / 2开始逐一向下过滤
15 {
16 //下面的操作和删除元素是一模一样的，只是不用将的元素个数减一
17 X = H->Data[j];
18 for (parent = j; 2 * parent <= H->Size; parent = child)
19 {
20 child = 2 * parent;
21 if (child != H->Size && H->Data[child] < H->Data[child + 1])
22 child++;
23 if (H->Data[child] < X)
24 break;
25 else
26 H->Data[parent] = H->Data[child];
27 }
28 H->Data[parent] = X;
29 }
30 return H;
31 }打印堆中的元素：
1 //打印堆中元素
2 void printHeap(MaxHeap H)
3 {
4 for (int i = 1; i <= H->Size; i++)
5 printf("%d ", H->Data[i]);
6 printf("
");
7 }先序建立树：
1 void PreOrderCreateHeap(MaxHeap H, int index)
2 {
3 int dt;
4 scanf_s("%d", &dt);
5 if (dt == 0)
6 {
7 return;
8 }
9 H->Size++;
10 H->Data[index] = dt;
11 printf("please enter the left child of %d :", dt);
12 PreOrderCreateHeap(H, 2 * index);
13 printf("please enter the right child of %d: ", dt);
14 PreOrderCreateHeap(H, 2 * index + 1);
15 }主函数：
1 int main()
2 {
3 MaxHeap H = CreateMaxHeap();
4 PreOrderCreateHeap(H, 1);
5 printHeap(H);
6
7 return 0;
8 }