c++优先队列 priority_queue 二叉堆 最大堆实现
发布时间
阅读量：
阅读量
文章目录
-
前言
-
一、priority_queue使用方式
-
- 1.初始化方式
- 2.成员函数
-
二、 二叉最大堆的实现原理
-
三、自己实现的priority_queue 最大堆代码
前言
c11 stl中提供优先队列的数据结构，可以实现最大堆和最小堆
一、priority_queue使用方式
1.初始化方式
std::prioriry_queue<int> tmp; //默认最大堆
std::priority_queue<int, vector<int>, std::greater<int>> tmp; //最小堆定义方式2.成员函数
二、 二叉最大堆的实现原理
- 基于数组结构实现的二叉堆具有布局紧凑的特点。
- 根据上述特点可知，在计算过程中可得出以下结论：父节点的位置为(i-1)/2；左子节点位于第2i+1位；右子节点位于第2i+2位。
- 当向堆中添加一个新的元素时，则需要将其与其进行比较操作。如果新插入的元素值大于当前父节点值，则需执行上移操作。
- 当删除堆顶的最大元素时，则需将最后一个元素移动至堆顶位置上，并随后与左右子节点进行比较判断。如果该移动后的元素小于其左右子节点中的最大值，则需执行下移操作以维持最大值所在的位置。
参考 二叉堆的实现
三、自己实现的priority_queue 最大堆代码
#include <iostream>
#include <vector>
using namespace std;
/*========================
简易priority_queue实现,只实现了最大堆
========================*/
// 由于二叉堆的特性
// 二叉堆中父节点位置是 (i - 1)/2
// 左子节点位置是 2*i + 1 右子节点位置是 2*i + 2
template <class T>
class priority_queue {
private:
// 二叉堆底层采用数组存放
vector<T> heap_;
private:
// 堆尾插入一个新值后，需要向上调整堆
void up_adjust() {
int pos = heap_.size() - 1;
// 将最后一个元素与父节点比较，如果比父节点大，向上移动
while (pos - 1 >= 0 && heap_[(pos - 1)/2] < heap_[pos]) {
swap(heap_[(pos - 1)/2], heap_[pos]);
pos = (pos - 1)/2;
}
}
// 从堆顶删除最大值后，需要向下调整堆
void down_adjust() {
int pos = heap_.size() - 1;
int parent_pos = 0;
int child_pos = parent_pos * 2 + 1;
while (child_pos <= pos) {
// 左右子节点相互比较选出大的
if (child_pos < pos && heap_[child_pos] < heap_[child_pos + 1]) {
child_pos++;
}
if (heap_[child_pos] < heap_[parent_pos]) break;
// 如果比其中较大的子节点小，向下移动
swap(heap_[child_pos], heap_[parent_pos]);
parent_pos = child_pos;
child_pos = parent_pos * 2 + 1;
}
}
public:
priority_queue() {
}
~priority_queue() {
}
T top() {
return heap_.front();
}
void push(T t) {
heap_.push_back(t);
up_adjust();
}
void pop() {
if (heap_.empty()) return;
int pos = heap_.size() - 1;
// 将最后一个元素覆盖掉第一个元素
heap_[0] = heap_[pos];
// 删除最后一个元素相当于删除第一个元素
heap_.pop_back();
down_adjust();
}
bool empty() {
return heap_.empty();
}
};
int main() {
priority_queue<int> pq;
pq.push(1);
pq.push(2);
pq.push(6);
pq.push(4);
pq.pop();
pq.push(9);
while (!pq.empty()) {
cout << pq.top() << endl;
pq.pop();
}
return 0;
}全部评论 (0)
还没有任何评论哟~