1. 优先级队列
1.1 基本原理
仿照C++ STL 中的优先级队列priority_queue,主要实现以下功能:
- 向队列中添加元素后,队列自动调整,保证队列中优先级最高的元素在队列头部(优先级可以定义比较函数,按照大小或者其他条件决定);
- 每次出队元素是队列中优先级最高的,因此优先级队列不满足先进先出的原则,而是根据每次都是优先级最高的先出。
优先级队列ADT的API如下:
方法名 | 功能 |
push() | 添加一个元素 |
pop() | 删除一个元素 |
top() | 获取队列顶部元素 |
size() | 获取队列大小 |
empty() | 返回队列是否为空 |
1.2 上浮和下沉
- 上浮:由下至上的堆有序化,对大顶堆(堆顶元素是堆中最大的)来说,如果子节点value大于父节点,那么就需要交换子节点和父节点,将子节点上浮,使其处于合适的位置,循环往复,直到父节点大于当前value,或者value达到堆顶,结束。
- 下沉:由上至下的堆有序化。对大顶堆来说,如果父节点value小于其子节点,需要将其与子节点交换,父节点value下沉,使其处于合适的位置,循环往复,直到value大于其子节点或者到堆的尾部。
2. 代码实现
2.1 push()
template<typename T, typename compare>
void MyPriorityQueue<T, compare>::push(T key)
{
//key添加到队尾
_pq.push_back(key);
_size++;
//如果只有一个元素,return
int idx = _size - 1;
if (idx == 0)return;
//上浮,key大于其父节点,即上浮(将父节点换到下面),idx的父节点是(idx -1) / 2
while (idx > 0 && _cmp(_pq[(idx -1) / 2], key)) {
_pq[idx] = _pq[(idx - 1) / 2];//将父节点换到下面
idx = (idx - 1) / 2;//更新idx,直到idx的父节点大于key,停止
}
_pq[idx] = key;//将key放到正确的位置
}
2.2 pop()
//将顶部元素删除,将尾部元素替换到顶部,然后下沉该元素
template<typename T, typename compare>
void MyPriorityQueue<T, compare>::pop()
{
if (_size == 0)return;
if (_size == 1) {
_pq.clear();
_size = 0;
return;
}
//将末尾的元素换到头部,末尾的pop出去
_pq[0] = _pq[_size-1];
_pq.pop_back();
//然后下沉新换到头部的元素
_size--;
int idx = 0;
T tmp = _pq[0];
int leftChild = 2 * (idx + 1) - 1;
int rightChild = 2 * (idx + 1);
while (leftChild < _size) {
//child,记录下沉到左子节点还是右子节点,还是不动
int child = idx;
if (_cmp(tmp, _pq[leftChild]))child = leftChild;
if (rightChild < _size && _cmp(_pq[child], _pq[rightChild]))child = rightChild;
if (idx == child)break;
_pq[idx] = _pq[child];//将child浮上去,child的位置暂时给tmp
idx = child;
leftChild = 2 * (idx + 1) - 1;//如果idx还存在左右子节点,继续;否则退出
rightChild = 2 * (idx + 1);
}
_pq[idx] = tmp;
}
2.3 完整代码
PriorityQueue.h
#pragma once
#include <vector>
using std::vector;
//vector做容器,函数对象compare用于比较,less对应大顶堆,greater对应小顶堆
template<typename T, typename compare = std::less<T>>
class MyPriorityQueue {
private:
size_t _size = 0;
vector<T> _pq;
compare _cmp;
public:
MyPriorityQueue() {}
~MyPriorityQueue() {};
void push(T key);
void pop();
T top();
void clear();
size_t size() { return _size; }
bool empty() { return _size == 0 ? true : false; }
};
//添加新元素到队尾,然后上浮该元素
template<typename T, typename compare>
void MyPriorityQueue<T, compare>::push(T key)
{
//key添加到队尾
_pq.push_back(key);
_size++;
//如果只有一个元素,return
int idx = _size - 1;
if (idx == 0)return;
//上浮,key大于其父节点,即上浮(将父节点换到下面),idx的父节点是(idx -1) / 2
while (idx > 0 && _cmp(_pq[(idx -1) / 2], key)) {
_pq[idx] = _pq[(idx - 1) / 2];//将父节点换到下面
idx = (idx - 1) / 2;//更新idx,直到idx的父节点大于key,停止
}
_pq[idx] = key;//将key放到正确的位置
}
//将顶部元素删除,将尾部元素替换到顶部,然后下沉该元素
template<typename T, typename compare>
void MyPriorityQueue<T, compare>::pop()
{
if (_size == 0)return;
if (_size == 1) {
_pq.clear();
_size = 0;
return;
}
//将末尾的元素换到头部,末尾的pop出去
_pq[0] = _pq[_size-1];
_pq.pop_back();
//然后下沉新换到头部的元素
_size--;
int idx = 0;
T tmp = _pq[0];
int leftChild = 2 * (idx + 1) - 1;
int rightChild = 2 * (idx + 1);
while (leftChild < _size) {
//child,记录下沉到左子节点还是右子节点,还是不动
int child = idx;
if (_cmp(tmp, _pq[leftChild]))child = leftChild;
if (rightChild < _size && _cmp(_pq[child], _pq[rightChild]))child = rightChild;
if (idx == child)break;
_pq[idx] = _pq[child];//将child浮上去,child的位置暂时给tmp
idx = child;
leftChild = 2 * (idx + 1) - 1;//如果idx还存在左右子节点,继续;否则退出
rightChild = 2 * (idx + 1);
}
_pq[idx] = tmp;
}
//返回堆顶元素
template<typename T, typename compare>
inline T MyPriorityQueue<T, compare>::top()
{
if (empty()) throw("Priority queue is empty!");
return _pq[0];
}
//清空堆
template<typename T, typename compare>
inline void MyPriorityQueue<T, compare>::clear()
{
_pq.clear();
_size = 0;
}
PriorityQueue.cpp
#include <iostream>
#include"PriorityQueue.h"
using namespace std;
int main()
{
MyPriorityQueue<int> pq1;
pq1.push(1);
pq1.push(3);
pq1.push(5);
pq1.push(7);
pq1.pop();
pq1.pop();
pq1.pop();
pq1.pop();
try {
bool a = pq1.empty();
int top = pq1.top();
}
catch (const char* e) {
cerr << e << endl;
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)