阅读量:0
基本概念
既然是通过二叉堆来实现一个优先队列，那么我们需要先知道什么是二叉堆，实际上，二叉堆的本质就是一个数组，只是我们从逻辑上将这个数组看作一颗完全二叉树，而这颗完全二叉树就是二叉堆。
二叉堆又分为小根堆和大根堆，要判断一个二叉堆是哪种类型，首先要找到第一个非叶子节点的数组索引，假如数组的末尾元素索引是n，那么第一个非叶子节点的数组索引就是(n-1)/2。
比如如图所示二叉堆的第一个非叶子节点的元素就是5。
由此引出大根堆的性质，当i>=0并且i<=(n-1)/2时，如果arr[i]>arr[2*i+1]并且arr[i]>arr[2*i+2]，也就是当前数组的节点i的元素的值，不仅大于其右孩子的值也大于其左孩子的值，对于整个数组的i都是如此，那么这个二叉堆就是一个大根堆。
相应的如果arr[i]<arr[2*i+1]并且arr[i]<arr[2*i+2]，这个二叉堆就是一个小根堆。
堆的操作
如果要向一个二叉堆中增加元素，也就是入堆操作，那么添加的元素只能在数组的末尾，然后判断元素是否需要进行上浮操作，调整元素的位置，使其满足这个二叉堆的性质。
如果要删除一个二叉堆中的元素，也就是出堆操作，那么删除的元素只能是堆顶元素也就是数组的0号位元素，并且用数组的末尾元素将数组的0号位元素进行覆盖，并判断覆盖后的0号位元素是否需要进行下沉操作。
对于二叉堆来说，由于它本身的二叉树结构，因此入堆和出堆的时间复杂度都是log(n)。
代码实现
要通过二叉堆实现一个优先队列，实际上就是将二叉堆的下沉和上浮操作进行封装，达到一个入队列和出队列的操作。
class PriorityQueue { using Cmp = std::function<bool(int, int)>; private: int size;//队列中的元素个数 int cap;//队列占用的总空间大小(以元素大小为单位) int* que;//指向动态数组的指针 Cmp cmp; public: PriorityQueue(int cap = 20, Cmp cmp = std::greater<int>()) :size(0), cmp(cmp), cap(cap) { que = new int[cap]; } PriorityQueue(Cmp cmp) :cmp(cmp),size(0), cap(20) { que = new int[cap]; } ~PriorityQueue() { delete[]que; que = nullptr; } //入堆函数 void push(int val) { if (size == cap) { int* p = new int[cap * 2]; memcpy(p, que, cap*sizeof(int)); delete[]que; que = p; cap *= 2; } if (size == 0) { que[size] = val; } else { siftup(size, val); } size++; } //出堆函数 void pop() { if (size == 0)throw "the queue is empty"; size--; if (size > 0) { siftdown(0, que[size]); } } //上浮函数 void siftup(int i,int val) { //最多上浮到首元素 while (i > 0) { int father = (i - 1) / 2;//从孩子的索引推出父亲的索引 if (cmp(val,que[father])) { que[i]=que[father]; i = father; } else { break; } } que[i] = val; } //下沉函数 void siftdown(int i, int val) { //不能下沉超过第一个非叶子节点 while (i <= (size - 1 - 1) / 2)//(n-1)/2 { int child = 2 * i + 1; //找到两个孩子中，满足条件的孩子 if (child + 1 < size && cmp(que[child + 1], que[child])) { child = child + 1; } if (cmp(que[child], val)) { que[i] = que[child]; i = child; } else { break; } } que[i] = val; } bool empty() const { return size == 0; } int getsize()const { return size; } int top()const { if (size == 0) throw "que is empty"; return que[0]; } };这里我使用了一个函数对象作为构造函数的传入参数，这样用户就可以自己定义优先队列的构造机制，可以是小根堆也可以是大根堆，用户只需要自己定义传入的函数对象就可以了，默认的话就是大根堆。
测试代码
int main() { PriorityQueue que; srand(time(NULL)); for (int i = 0; i < 10; i++) { que.push(i+1); } while(!que.empty()) { std::cout << que.top()<< " "; que.pop(); } return 0; }从输出结果也可以发现，大根堆每次出堆的都是整个数组中的最大元素。
