优先队列---二叉堆：
二叉堆是一棵完全二叉树，最大堆（最小堆）中，所有根节点的键值都要比对应的子树要大（小）。
由于是完全二叉树，所以存储结构可以采用数组。
最大堆的创建：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<string.h>
#include<cstdlib>
#define INF 0x3f3f3f3f
typedef int ElementType;
using namespace std;struct HeapNode {ElementType *Elements;int Size;//当前个数int Capacity;//最大容量
};typedef struct HeapNode *MaxHeap;MaxHeap Create(int MaxSize)
{MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapNode));H->Elements = (ElementType*)((MaxSize + 1) * sizeof(ElementType));H->Size = 0;H->Capacity = MaxSize;H->Elements[0] = INF;//哨兵return H;
}最大堆的插入：
思想：先把待查元素放在数组的最后一个位置，然后和它的父亲去比较大小，如果比他父亲节点值大，则和它父亲互换，然后再依次和父亲节点比较大小，直到比父亲节点值小为止。为了减少互换的操作，可以先去找到最后待查元素的位置再去放（这样就有一个空穴）。---这一策略叫做上滤（空穴往上走）
数组0处放哨兵，卡住边界。
void Insert(MaxHeap H, ElementType item)
{if (H->Size >= H->Capacity){cout << "满" << endl; return;}int i = ++H->Size;for (; H->Elements[i / 2] < item; i /= 2)//0处有哨兵。H->Elements[i] = H->Elements[i / 2];//上面的往下面走。直到i的父节点中的值大于item。H->Elements[i] = item;//放
}
最大堆的删除：
思想：把根节点元素返回。数组最后一个元素（tmp）先放在根节点位置（1位置），然后再去调整堆的顺序性，类似于插入，根节点元素值和儿子节点最大值相比较，如果前者比后者小，就互换，依次互换下去，直到tmp大于两个儿子节点的大小位置。
为了减少互换的操作，同样可以先找到tmp最后放的位置，由于这次空穴往下走，所以该策略叫做下滤。
ElementType DeleteMax(MaxHeap H)
{int parent, child;ElementType maxitem, tem;if (H->Size == 0) { cout << "空" << endl; return; }maxitem = H->Elements[1];//最大值，便于后面返回。tem = H->Elements[H->Size--];for (parent = 1; parent * 2 <= H->Size; parent = child){child = parent * 2;if (child != H->Size&&H->Elements[child] < H->Elements[child + 1])child++;if (tem >= H->Elements[child])break;else H->Elements[parent] = H->Elements[child];//下面的往上走，直到遇到tem大于下面的两个儿子为止。}H->Elements[parent] = tem;//放return maxitem;
}
最大堆的建立：
方法1：通过插入操作，依次将N个元素插入一个初始化为空的堆中。时间复杂度为O（NlogN）。
方法2：先将N个元素按输入顺序存入数组，然后调整各个节点的位置，以满足最大堆的有序性。
调整办法：从倒数第一个有儿子的节点开始依次调整，这样就能保证下面的堆序。类似于删除的操作，每次将要调整的子堆根节点拿出来，然后下滤，找到根节点的位置，放入即可。
这种方法的时间复杂度为是N。
void PercDown(MaxHeap H ,int p )
{int Parent, Child;ElementType X;X = H->Elements[p];for (Parent = p; Parent * 2 <= H->Size; Parent = Child ){Child = Parent * 2;if ((Child != H->Size) && (H->Elements[Child]<H->Elements[Child + 1]))Child++;if (X >= H->Elements[Child]) break; else H->Elements[Parent] = H->Elements[Child];}H->Elements[Parent] = X;
}
void BuildHeap(MaxHeap H )
{int i;for (i = H->Size / 2; i>0; i--) PercDown(H, i );
}