堆数据结构

堆是一棵完全二叉树，通常用数组存储，满足父节点与子节点之间的优先级关系。常见的操作包括建堆、插入与删除堆顶元素。

建堆

堆可以通过逐个插入实现，也可以把一个无序数组当成堆底结构，自底向上依次向下调整以建立最大堆或最小堆。

插入

新元素先放到堆尾，再向上调整（父节点索引 (i-1)/2）：如果子节点的值比父节点更大，就交换，直到堆性质恢复。

删除

默认只能直接删除堆顶。删除流程是把堆尾元素取代堆顶，再从上往下调整以恢复堆性质。如果想删除堆中间的某个元素，通常的做法是不断 pop() 弹出堆顶，遇到目标元素后再把弹出的值按原顺序重新插入。

代码（最大堆）

#include<iostream>
#include<vector>
using namespace std;

class MaxHeap{

    public:
    vector<int> heap;
    MaxHeap(vector<int>& nums){
        heap = nums;
        for(int i= nums.size()/2-1;i>=0;i--){
            tiao_zheng_down(i);
        }
    }

    void push(int num){
        heap.push_back(num);
        tiao_zheng_up();  // 插入新元素时，从堆尾向上调整
    }

    void pop(){
        swap(heap[0],heap[heap.size()-1]);
        heap.pop_back();
        tiao_zheng_down(0);
    }

    int top(){
        return heap[0];
    }

    void tiao_zheng_up(){
        int child_index = heap.size()-1;
        while(child_index>0){
            int parent_index = (child_index-1)/2;
            if(heap[child_index]>heap[parent_index]){
                swap(heap[child_index],heap[parent_index]);
                child_index = parent_index;
            }else{
                break;
            }
        }
    }

    void tiao_zheng_down(int index){
        while(true){
            int left_child = 2*index+1;
            int right_child = left_child+1;
            int real_index = index;
            if(left_child<heap.size()&&heap[left_child]>heap[real_index]){
                real_index = left_child;
            }
            if(right_child<heap.size()&&heap[right_child]>heap[real_index]){
                real_index = right_child;
            }
            if(real_index!=index){
                swap(heap[index],heap[real_index]);
                index = real_index;
            }else{
                break;
            }
        }
    }

};

int main(){
    vector<int> nums;
    MaxHeap maxHeap(nums);
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(5);
    maxHeap.push(30);
    cout<<maxHeap.top()<<endl;

    maxHeap.pop();
    cout<<maxHeap.top()<<endl;

}

自定义结构体作为元素

如果需要按照结构体的某个字段排序，可以通过传入自定义的比较器。例如下面的 CompareTask 返回 true 时说明第一个参数优先级更低，于是 priority_queue 会把优先级大的放在前面，top() 始终返回当前最高优先级任务。

#include <iostream>
#include <queue>
#include <vector>

struct Task {
    int priority;
    std::string description;

    Task(int p, const std::string& desc) : priority(p), description(desc) {}
};

struct CompareTask {
    bool operator()(const Task& t1, const Task& t2) const {
        return t1.priority < t2.priority; // 优先级大的在前
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, CompareTask> pq;

    pq.push(Task(5, "Write report"));
    pq.push(Task(1, "Fix critical bug"));
    pq.push(Task(3, "Attend meeting"));

    while (!pq.empty()) {
        Task t = pq.top();
        pq.pop();

        std::cout << "Processing task: " << t.description
                  << " with priority: " << t.priority << std::endl;
    }

    return 0;
}