优先队列和堆

优先队列和堆

1、优先队列

能够完成一下操作的队列叫优先队列：
1. 插入一个数值
2. 取出最小的数值（获得值并删除）

能够使用二叉高效解决上述问题的，是一种叫做堆(实际上堆有不同的数据结构，这里叫做二叉堆的数据结构)的数据结构。

2、堆的结构

堆的结构为二叉树：
堆的主要二叉树特性为：
1、所有的儿子节点的值一定不小于父亲节点值。
2、树的节点是重上到下，从左往右的顺序紧凑排列的。

向堆中插入数值，其首先将插入值放在二叉树末尾，然后根据其值的大小往上移动。

上面的一组图片展示了如何插入数据。很明显的是每次插入并调整堆后，堆的顶端保持为最小值的节点。
当我们取出最小根后，再次调整堆。

堆的复杂度

堆的加入和取出操作花费时间都和堆的深度成正比。如果有n个元素，那么每个操作可以O(logn)$O(logn)$的时间内完成。

堆的实现

我们采用数组来存储二叉树。儿子节点满足一下性质：

1. 左儿子的编号为自己编号×2+1；
2. 右儿子的编号为自己编号×2+2；

#include <iostream>

#define MAX_N 1000

using namespace std;

class ArrayHeap {

private:
    int heap[MAX_N], sz = 0;

public:


    void push(int x) {
        int i = sz++; //i表示加入的节点的编号
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[p] <= x) break;  //不用调整

            heap[i] = heap[p];
            i = p;
        }
        heap[i] = x;
    }


    int pop() { //pop操作时，将最后一层的最右边一个节点x取出，重新调整各节点将x安放在合适的位置
        int ret = heap[0];
        int x = heap[--sz]; //sz表示个数，而数组是从0号开始，所以--sz
        //从根开始向下交换
        int i = 0;
        while (i * 2 + 1 < sz) {  //此条件表白i号结点的左右孩子都存在，左孩子小于sz表明右孩子小于或等于sz
            int lc = i * 2 + 1, rc = i * 2 + 2; //lc,rc分别为左右孩子的标号。
            if (rc < sz && heap[rc] < heap[lc]) lc = rc;  //将较小的孩子节点编号给lc

            if (heap[lc] >= x) break; //如果已经没有大小颠倒

            heap[i] = heap[lc]; //将较小的提上来
            i = lc;
        }
        heap[i] = x;

        return ret;
    }
};

实际使用中我们大可不必自己编写堆的实现，在c++标准模板库STL中已经为我们准备了priority_queue类，该类为大根堆，即每次取出的都是最大值。

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int main(){

    priority_queue<int> pque;

    srand((unsigned)time(NULL));
   for(int i=0;i<100;i++){
       pque.push(rand()%100);
   }


  while(!pque.empty()){
      cout<<pque.top()<<"\t";
      pque.pop();
  }

    return 0;
}