·堆

一、堆的定义：

    堆是一颗完全二叉树。

二、分类：

    分为最大堆和最小堆。最大堆是树中每个节点的值都大于或等于其左右孩子节点的值的堆，最小堆是树中每个节点的值都小于或者等于其左右孩子节点的值的堆。

三、向下调整运算

    假设构造最大堆，我们使用向下调整运算来实现。

    向下调整运算：在原本已是最大堆的树中插入新的值后，新加入的值可能会影响树的状态，需要对其进行调整。一般是先比较新的值与父节点的大小关系，按此步骤往上调整。调整完后在进行二次调整，还原树的最大堆的形态。

//代码展示

void AdjustHeap(int Heap[] ,int s, int m){

//假设Heap[s+1...m]已是最大堆，现将其调整为Heap[s...m]为根的最大堆

    int Temp=Heap[s];

    for(j=2*s;j<=m;j*+2){

        if(j<m&&Heap[j]<Heap[j+1])

            j++;

        if(Temp>Heap[j])break;

        Heap[s]=Heap[j];

        s=j;

}

    Heap[s]=Temp;

}

·优先权队列

    优先权队列是0个或者多个元素的集合，每个元素都有一个优先权或值。我们主要对优先权队列执行（1）查找；（2）插入新元素；（3）删除。

堆是一种能有效实现优先权队列的一种数据结构。对优先权队列执行删除操作时，最小堆删除的时最小的元素，最大堆删除的是最大的元素，对应的也就是堆顶元素。