不使用STL实现优先队列
时间: 2023-07-09 16:11:52 浏览: 60
优先队列是一种特殊的队列,可以根据元素的优先级自动排序,最常见的实现方式是使用堆(heap)。以下是一个使用堆实现优先队列的示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
class PriorityQueue {
public:
PriorityQueue() {}
void push(int val) {
heap.push_back(val);
int idx = heap.size() - 1;
while (idx > 0 && heap[idx] > heap[(idx - 1) / 2]) {
swap(heap[idx], heap[(idx - 1) / 2]);
idx = (idx - 1) / 2;
}
}
void pop() {
int lastIdx = heap.size() - 1;
swap(heap[0], heap[lastIdx]);
heap.pop_back();
int idx = 0;
while (2 * idx + 1 < heap.size()) {
int maxChildIdx = 2 * idx + 1;
if (maxChildIdx + 1 < heap.size() && heap[maxChildIdx + 1] > heap[maxChildIdx]) {
maxChildIdx++;
}
if (heap[idx] < heap[maxChildIdx]) {
swap(heap[idx], heap[maxChildIdx]);
idx = maxChildIdx;
} else {
break;
}
}
}
int top() {
return heap[0];
}
bool empty() {
return heap.empty();
}
private:
vector<int> heap;
};
```
在这个实现中,我们使用一个动态数组来存储队列中的元素,然后通过堆的方式来维护元素的优先级顺序。具体来说,我们使用一个大根堆来实现优先队列,每次插入元素时,我们将其插入到堆的末尾,然后不断将其与其父节点比较,如果比父节点优先级高,则交换位置,直到找到合适的位置。删除元素时,我们将堆顶元素与最后一个元素交换位置,然后弹出最后一个元素,最后不断将堆顶元素与其子节点比较,如果比子节点优先级低,则交换位置,直到找到合适的位置。获取队列首元素时,直接返回堆顶元素即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)