c++优先队列大根堆代码模板
时间: 2023-05-27 08:01:11 浏览: 70
// 定义一个大根堆类
class MaxHeap {
private:
vector<int> heap; // 使用 vector 存储堆
int size; // 堆的大小
// 工具函数 —— 交换堆中的两个元素
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 工具函数 —— 堆化某一个节点
void heapify(int index) {
int largest = index; // 先将当前节点标记为最大值
int left = index * 2 + 1; // 左孩子节点的索引
int right = index * 2 + 2; // 右孩子节点的索引
// 比较当前节点、左孩子节点和右孩子节点中的最大值
if (left < size && heap[left] > heap[largest]) {
largest = left;
}
if (right < size && heap[right] > heap[largest]) {
largest = right;
}
// 如果当前节点的值不是最大值,则将当前节点和最大值节点交换,并递归地对最大值节点进行堆化
if (largest != index) {
swap(heap[index], heap[largest]);
heapify(largest);
}
}
public:
// 构造函数 —— 建立一个空堆
MaxHeap() {
size = 0;
}
// 获取堆中元素的数量
int getSize() {
return size;
}
// 判断堆是否为空
bool isEmpty() {
return size == 0;
}
// 在堆末尾添加一个元素,并将其上移对其进行调整
void add(int element) {
heap.push_back(element);
size++;
int index = size - 1;
int parent = (index - 1) / 2;
while (index > 0 && heap[index] > heap[parent]) {
swap(heap[index], heap[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
// 获取堆顶元素
int peek() {
if (size == 0) {
throw "Heap is empty.";
}
return heap[0];
}
// 删除堆顶元素,并将堆末尾的元素放到堆顶,然后将其下沉进行调整
int remove() {
if (size == 0) {
throw "Heap is empty.";
}
int root = heap[0];
heap[0] = heap[size - 1];
size--;
heap.pop_back();
heapify(0);
return root;
}
};