优先队列（堆）

优先级队列支持插入操作和删除操作，进行删除操作时总是删除最小元素，而进行插入操作时，先插入在队列末尾，然后再调整这个元素到一个合适的位置。

其实优先级队列只需要删除元素的时候能够删除最小元素即可，这是优先级队列最重要的性质。而对于插入元素，插入位置则并不固定，因此它的实现可以使用链表或者二叉查找树。不过这两种实现都并不是最优的。

实现优先级队列最优的办法是使用二叉堆。二叉堆的本质是完全二叉树，但是这棵完全二叉树的存储结构是一个数组，所有结点和它的父节点之间的编号存在严格的数学关系。

堆可以分为小根堆和大根堆。所以以下以小根堆为例。

堆的结构性和堆序性：

结构性：满足完全二叉树。

堆序性：父节点大于等于（或者小于等于）子结点。

堆的结构性和堆序性可以翻译为另外两个性质如下：

假设堆的编号从1开始，父节点的编号为i，则其左孩子编号为2i，右孩子编号为2i+1。假设堆的编号从0开始，父节点的编号为i，则其左孩子编号为2i+1，右孩子编号为2i+2。

大根堆中的所有结点，父节点总是比左孩子和右孩子都大。

第1节堆插入

插入元素在数组末尾，然后再调整新元素的位置。

这个操作也被称为堆的上浮调整。

void heapinsert(int arr[],int len,int index)
{
    // 当index==0或者arr[index]小于其父节点时停止
    while(arr[index]>arr[(index-1)/2])
    {
        swap(arr,index,(index-1)/2);
        index=(index-1)/2;
    }
}

第2节堆删除

删除根结点，然后调整其余元素，使得剩下的元素仍然是堆。

假设我们直接去掉根结点，那么这个堆的根结点就成为一个空穴，然后再去调整剩下的元素，总是挑选左右孩子中的较小一个来代替空穴，这样最后空穴一定会落到最低的一层，最后将末尾元素和空穴交换即可。

但是假入我们直接划掉这个堆的最后一个元素，然后把该元素用来替换堆的根结点，然后再调整该元素的位置，那么看起来就要方便多了。两者的本质一样。

这个操作也被称之为堆的下沉。

int pop(int heap[],int heapSize)
{
    int ans=heap[0];
    swap(heap,0,--heapSize);
    heapfiy(heap,0,heapSize);
    return ans;
}

// 堆的下沉
void heapfiy(int arr[],int index,int heapSize)
{
    int left=index*2+1;
    while(left<heapSize)
    {
        int largest=left+1&&arr[left+1]>arr[left]?left+1:left;
        largest=arr[largest]>arr[index]?largest:index;
        if(index=largest)
        {
            break;
        }
        swap(arr,largest,index);
        index=largest;
        left=index*2+1；
    }
}

第3节堆的应用

堆排序：不断删除堆的根结点，然后调整堆，这样所有被删除的元素就是有序的。在实际中，只要把堆的末尾元素和堆的根结点进行交换，然后不断调整堆，当堆的元素个数为0的时候就可以看作是排序完成。所以，假设我们要对一个数组进行排序，首先还是需要先生成堆，然后再进行堆排序。

生成大根堆：

方法一（自顶向下）：对一个空堆进行n次堆插入即生成大根堆。

方法二（自底而上）：先将二叉树的底层调整成堆，然后再进行下沉操作。

void heapSort(int arr[],int len)
{
    if(len<2)
    {
        return;
    }
    // 生成堆
    for(int i=len-1;i>=0;i--)
    {
        heapfiy(arr,i,len);
    }

    // 借助堆排序
    int heapSize=len;
    swap(arr,0,--heapSize); //其实这句应该是多余的，只要交换下面循环中两条语句的顺序即可
    while(heapSize>0)
    {
        heapfiy(arr,0,heapSize);
        swap(arr,0,--heapSize);
    }
}