大根堆c++优先队列实现
时间: 2024-08-13 20:03:00 浏览: 34
大根堆(Max Heap)是一种特殊的完全二叉树,其中每个节点的值都大于或等于其子节点的值,通常用于实现优先队列,因为最小元素总是在根部。在C++中,标准库`std::priority_queue`就是基于最大堆的数据结构。
以下是使用C++实现一个简单的最大堆优先队列的基本步骤:
```cpp
#include <queue>
#include <vector>
// 使用vector作为底层存储,因为它的内部是动态调整大小的,适合堆操作
template<typename T>
class MaxHeap {
private:
std::vector<T> heap;
int size;
public:
// 构造函数,初始化一个空的最大堆
MaxHeap() : size(0) {}
// 插入元素并调整堆结构
void push(T value) {
heap.push_back(value);
siftUp(size - 1);
size++;
}
// 删除并返回堆顶元素(最大值)
T pop() {
if (size == 0) return T();
T max_val = heap;
heap = heap[size - 1]; // 将最后一个元素移到顶部
heap.pop_back(); // 减小堆大小
siftDown(0); // 调整堆结构
return max_val;
}
// 其他辅助方法
bool empty() const { return size == 0; }
int size() const { return size; }
private:
// siftUp方法用于向上调整堆
void siftUp(int i) {
while (i > 0 && heap[parent(i)] < heap[i]) {
swap(heap[i], heap[parent(i)]);
i = parent(i);
}
}
// siftDown方法用于向下调整堆
void siftDown(int i) {
while (true) {
int left = leftChild(i), right = rightChild(i);
int largest = i;
if (left < size && heap[left] > heap[largest])
largest = left;
if (right < size && heap[right] > heap[largest])
largest = right;
if (largest != i) {
swap(heap[i], heap[largest]);
i = largest;
} else {
break;
}
}
}
// 辅助函数获取父节点、左孩子和右孩子的索引
int parent(int i) const { return (i - 1) / 2; }
int leftChild(int i) const { return 2 * i + 1; }
int rightChild(int i) const { return 2 * i + 2; }
};
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](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)