- 前言
- 一、优先队列的优点
- 二、具体实现方法
- 代码
- 总结
前言
提示:本文用C++实现了优先队列:
一、优先队列的优点
优先队列(priority queue)可以在 O(1) 时间内获得最大值,并且可以在 O(log n) 时间内取出
最大值或插入任意值。
优先队列常常用堆(heap)来实现。堆是一个完全二叉树,其每个节点的值总是大于等于子
节点的值。实际实现堆时,我们通常用一个数组而不是用指针建立一个树。这是因为堆是完全二
叉树,所以用数组表示时,位置 i 的节点的父节点位置一定为 i/2,而它的两个子节点的位置
又一定分别为 2i+1 和 2i+2。
以下是堆的实现方法,其中最核心的两个操作是上浮swim和下沉sink:如果一个节点比父节点大,那
么需要交换这个两个节点;交换后还可能比它新的父节点大,因此需要不断地进行比较和交换操
作,我们称之为上浮;类似地,如果一个节点比父节小,也需要不断地向下进行比较和交换操作,
我们称之为下沉。如果一个节点有两个子节点,我们总是交换最大的子节点。
代码如下:
#define N 1000 vector总结heap; //上浮 void swim(int pos) { while (pos > 0 && heap[pos/2] < heap[pos]) //父小于子 { swap(heap[pos/2], heap[pos]); //父子交换 pos = pos / 2; //以父为子 } } //下沉 void sink(int pos) { while (2 * pos + 1 <= N) //子节点不溢出 { int i = 2 * pos + 1; //i为pos的左儿子 // i不越界 左儿子小于右儿子 那就让右儿子和pos比较 if (i < N && heap[i] < heap[i+1]) ++i; //如果pos已经大于i的节点值 就不用交换了直接break if (heap[pos] >= heap[i]) break; swap(heap[pos], heap[i]); //否则就交换 pos = i; //更新pos为i } } //插入任意值: 把要插入的数放在最后一位,然后swim void push(int k) { heap.push_back(k); swim(heap.size() - 1); } //删除最大值(根): 把最后一个数字挪到开头,然后sink void pop() { heap[0] = heap.back(); heap.pop_back(); sink(0); } //获得最大值(根) int top() { return heap[0]; }
这里实现的是能快速获得最大值的优先队列,如果将算法中的大于小于号适当互换,就可以实现快速获得最小值的优先队列,当然,库中已经有了现成的priority_queue供我们使用
C++ priority_queue(STL priority_queue)用法详解