优先队列(Priority Queue)：特殊的"队列"，取出元素的顺序是依照元素的优先权(关键字)大小，而不是元素进入队列的先后顺序

堆的两个特性
  结构性：用数组表示的完全二叉树;
  有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)
    "最大堆(MaxHeap)"，也称"大顶堆"：最大值
    "最小堆(MinHeap)"，也称"小顶堆"：最小值
  通俗的来说就是最大堆的上面的那个要比连接下面两个都要大。最小堆则相反，最上面那个要比连接下面两个都要小。同时需要是完全二叉树
  注意：从根结点到任意结点路径上结点系列的有序性！

类型名称：最大堆(MaxHeap)
数据对象集：完全二叉树，每个结点的元素值不小于其子结点的元素值
操作集：最大堆H属于MAaxHeap,元素item属于ElementType，主要操作有：
1.MaxHeap Create(int MaxSize)：创建一个空的最大堆
2.Boolean IsFull(MaxHeap H)：判断最大堆H是否已满
3.Insert(MaxHeap H,ElementType item)：将元素item插入最大堆H
4.Boolean IsEmpty(MaxHeap H):判断最大堆H是否为空
5.ElementType DeleteMax(MaxHeap H)：返回H中最大元素(高优先级)

typedef struct HeapStruct *MaxHeap;
struct HeapStruct{
    ElementTye *Elements;//存储堆元素的数组
    int Size;//堆的当前元素个数
    int Capacity;//堆的最大容量
};
MaxHeap Create(int MaxSize)
{
    //创建容量为MaxSize的空的最大堆
    MaxHeap H = malloc(sizeof(struct HeapStruct));
    H->Elements = malloc((Maxsize+1)* sizeof(ElementType));//Maxsize+1是希望申请的容量
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Elements[0] = MaxSize;
    H->Elements[0] = MaxData;
    //定义"哨兵"为大于堆中所有可能元素的值，便于以后更快操作
    return H;
}

void Insert(Maxheap H,ElementType item)
{
    //将元素item插入最大堆H,其中H->Elements[0]已经定义为哨兵
    int i;
    if(IsFull(H)){
    printf("最大堆已满");
    return;
}
i = ++H->Size;//i指向插入后堆中的最后一个元素的位置
for(;H->Elements[i/2]) < item;i/=2)
    H->Elements[i] = H->Elements[i/2];//向下过滤结点
H->Elements[i] = item;//将item插入
}
复杂度：T(N) = O(log N)

ElementType DeleteMax(MaxHeap H)
{
    //从最大堆H中取出键值为最大的元素，并删除一个结点
    int Parent,Child;
    ElementType MaxItem,temp;
    if( IsEmpty(H)){
        printf("最大堆已为空");
        return;
    }
    MaxItem = H->Elements[1];//取出根结点最大值，保存起来，最后是要return出去的
    //temp = H->Elements[H->Size--];
    for(Parent = 1;Parent*2 <= H->Size;Parent=Child){//Parent指示我将来要换的位置，退出循环就说明了我们要的位置找到了
        Child = Parent * 2;//Child指向左儿子
        if((Child != H->Size) && (H->Elements[Child] < H->Elements[Child+1]))
            Child++;//Child指向左右子结点的较大者
        if(temp > H->Elements[Child])break;
        else//移动temp元素到下一层
            H->Elements[Parent] = H->Elements[Child];
    }
    H->Elements[Parent] = temp;
    return MaxItem;
}
在完全二叉树里面，i代表一个节点，它的左儿子在2i,右儿子在2i+1
    如果左儿子2i已经超出Size的范围，说明左儿子已经在堆栈外面了，那就说明它没左儿子
    Parent*2 <= H->Size是判别它有没有左儿子，如果没有左儿子那右儿子肯定也没有那就退出循环了
    Child != H->Size：Child指向左儿子意味左儿子是最后一个元素了，那就意味着没有右儿子了。实际上这个就相当于判别有没有右儿子

建立最大堆：将已经存在的N个元素按最大堆的要求存放在一个一维数组中
方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为O(NlogN)
每次插入 它的时间复杂性是log2N
总共循环N遍，所以整个时间复杂性是Nlog2N
上方这个方法1的效率是不够的，我们可以有更好的方法
方法2：在线性时间复杂度下建立最大堆.
(1)将N个元素按输入顺序存入，先满足完全二叉树的结构特性
(2)调整各结点位置，以满足最大堆的有序特性

typedef struct HNode *Heap; /* 堆的类型定义 */
struct 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;
}
bool IsFull( MaxHeap H )
{
    return (H->Size == H->Capacity);
}
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;
}
#define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */
bool IsEmpty( MaxHeap H )
{
    return (H->Size == 0);
}
ElementType DeleteMax( MaxHeap H )
{ /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */
    int Parent, Child;
    ElementType MaxItem, X;
    if ( IsEmpty(H) ) {
        printf("最大堆已为空");
        return ERROR;
    }
    MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */
    /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
    X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
    for( Parent=1; Parent*2<=H->Size; Parent=Child ) {
        Child = Parent * 2;
        if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
        else  /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
    return MaxItem;
} 
/*----------- 建造最大堆 -----------*/
void PercDown( MaxHeap H, int p )
{ /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    ElementType X;
    X = H->Data[p]; /* 取出根结点存放的值 */
    for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
        Child = Parent * 2;
        if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
        else  /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }

if(score < 60 ) grade = 1;
else if(score < 70) grade = 2;
else if(score < 80) grade = 3;
else if(score < 90) grade = 4;
else grade = 5;

if(score < 80)
{
    if(score < 70 )
        if(score < 60) grade = 1;
    else grade = 2;
}else if(score < 90 )grade = 4;
else grade = 5;

typedef struct TreeNode *HuffmanTree;
struct TreeNode{
    int Weight;
    HuffmanTree Left,Right;
}
HuffmanTree Huffman(MinHeap H)
{
    //假设H->Size个权值已经存在H->Elements[]->Weight里
    int i; HuffmanTree T;
    BuildMinHeap(H);//将H->Elements[]按权值调整为最小堆
    for(i = 1;i < H->Size; i++){//做H->Size-1次合并
        T = malloc(sizeof(struct TreeNode));//建立新结点
        T->Left = DeleteMin(H);//从最小堆中删除一个结点，作为新T的左子结点
        T->Right = DeleteMin(H);//从最小堆中删除一个结点，作为新T的右子结点
        T->Weight = T->Left->Weight+T->Right->Weight;//计算新权值
        Insert(H,T);//将新T插入最小堆
    }
    T = DeleteMin(H);
    return T;
}
整体复杂度为O(NlogN)