【C++】优先队列

优先队结构的不同物理结构与常用操作算法

优先队列是一种特殊的队列,队列中的元素具有优先级,每次弹出操作会弹出优先级最高的元素。

优先队列常用的物理结构有:

1. 数组:简单但不高效,插入和删除操作需要移动大量元素,时间复杂度高。

2. 二叉堆:是一种完全二叉树,通常用数组表示。插入和删除操作时间复杂度为O(logn) 。

3. 二叉搜索树:节点值大于左子树所有节点,小于右子树所有节点。插入和删除操作时间复杂度取决于树的高度,平衡二叉搜索树时间复杂度为O(logn) 。

常用操作设计:

1. 插入元素:将新元素插入到合适的位置,维持堆的性质。

2. 删除最大/最小元素:删除根节点元素,并调整堆的结构。

3. 获取最大/最小元素:直接返回堆顶元素。

4. 堆大小:返回堆中的元素个数。

5. 堆空:判断堆是否为空。

使用数组结构实现最小堆的代码：

#include <iostream>using namespace std;template <typename T>
class PriorityQueue
{
private:T *arr;int capacity;int size;public:PriorityQueue(int cap)  //创造队列{capacity = cap;size = 0;arr = new T[cap];}int getSize(){return size;}bool isEmpty(){return size == 0;}void insert(T elem){if (size == capacity){return;}size++;arr[size - 1] = elem;int i = size - 1;while (i > 0 && arr[i] < arr[(i - 1) / 2]){swap(arr[i], arr[(i - 1) / 2]);i = (i - 1) / 2;}}T getMin() // 返回最小值{return arr[0];}T extractMin() // 提取最小值{if (isEmpty()){return -1;}T root = arr[0];arr[0] = arr[size - 1];size--;int i = 0;while (2 * i + 1 < size){int leftChild = 2 * i + 1;int rightChild = 2 * i + 2;if (rightChild < size && arr[leftChild] > arr[rightChild]){leftChild = rightChild;}if (arr[i] <= arr[leftChild]){break;}swap(arr[i], arr[leftChild]);i = leftChild;}return root;}bool find(T elem)  //查找{for (int i = 0; i < size; i++){if (arr[i] == elem){return true;}}return false;}void deleteElem(T elem)  //删除队列元素{if (isEmpty() || !find(elem)){return;}int i;for (i = 0; i < size; i++){if (arr[i] == elem){break;}}arr[i] = arr[size - 1];size--;while (i < size && arr[i] < arr[(i - 1) / 2]){swap(arr[i], arr[(i - 1) / 2]);i = (i - 1) / 2;}while (2 * i + 1 < size){int leftChild = 2 * i + 1;int rightChild = 2 * i + 2;if (rightChild < size && arr[leftChild] > arr[rightChild]){leftChild = rightChild;}if (arr[i] <= arr[leftChild]){break;}swap(arr[i], arr[leftChild]);i = leftChild;}}
};int main()
{PriorityQueue<int> pq(5);pq.insert(3);pq.insert(1);pq.insert(4);cout << pq.getMin() << endl;cout << pq.extractMin() << endl;cout << pq.getSize() << endl;pq.deleteElem(4);cout << pq.find(4) << endl;return 0;
}

运行结果截图：

最小堆和最大堆只有比较函数不同。最小堆使用 < 比较,最大堆使用 > 比较。所以要将最小堆修改为最大堆,只需要修改比较函数即可。这里对应的修改代码为：

T getMax() // 返回最大值 
{ return arr[0]; 
}T extractMax() // 提取最大值
{ if (isEmpty()) { return -1; } T root = arr[0]; arr[0] = arr[size - 1]; size--; int i = 0; while (2 * i + 1 < size) { int leftChild = 2 * i + 1; int rightChild = 2 * i + 2; if (rightChild < size && arr[leftChild] < arr[rightChild]) { leftChild = rightChild; }if (arr[i] >= arr[leftChild]) { break; } swap(arr[i], arr[leftChild]); i = leftChild; } return root; 
}

可以看到，这里把 < 改为 > ，将 getMin() 改为 getMax()，将 extractMin() 改为 extractMax()。这样，堆中最大的值会在堆顶,所以这就是一个最大堆了。