堆的定义及性质

堆是一棵完全二叉树，以大顶堆为例，每个节点的值不小于其左右孩子节点。用数组实现堆，下标为i的节点其左右孩子节点的小标为2i和2i+1。

相关操作

建堆：从最后一个有孩子的节点开始，逆序枚举，每个节点向下调整

插入元素：将新增元素插入堆尾，向上调整

删除（堆顶）元素：将最后一个元素覆盖堆顶，从堆顶向下调整

#include <bits/stdc++.h>
using namespace std;


const int maxn = 100; // 堆的总容量
int n;  // 堆内元素个数
vector<int>heap(100,0); // 以大顶堆为例
// 节点i的左右孩子节点下标为2i和2i+1

// 调整[low,high]范围内的节点
// 向下调整堆
void downAdjust(int low,int high)
{
    int i = low, j = i*2;
    while(j<=high)
    {
        // 如果右孩子存在且值大于左孩子
        if(j+1<=high && heap[j+1]>heap[j])
        {
            // 记住较大孩子的下标
            j = j+1;
        }
        // 如果孩子中的最大权值比欲调整的节点i要大，就交换
        if(heap[j]>heap[i])
        {
            int tmp = heap[i];
            heap[i] = heap[j];
            heap[j] = tmp;
            i = j;
            j = i*2;
        }
        else break; // 孩子节点的值均比根小
    }
}
// 在下标[low,high]范围内上调
void upAdjust(int low,int high)
{
    int i = high, j = i/2;
    while(j>=low)
    {
        // 大于根节点
        if(heap[i]>heap[j])
        {
            int tmp = heap[i];
            heap[i] = heap[j];
            heap[j] = tmp;
            i = j;
            j = i/2;
        }
        else break; // 没有比根节点大
    }

}
// 往堆内添加元素
void insert(int x)
{
    heap[++n] = x;
    upAdjust(1,n);
}

// 删除元素
void deleteTop()
{
    // 最后一个元素覆盖堆顶，再向下调整
    heap[1] = heap[n--];
    downAdjust(1,n);
}
//排序
void HeapSort()
{
    while(n>=1)
    {
         cout<<heap[1]<<" ";
         deleteTop();
    }
    cout<<endl;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>heap[i];
    //建堆，从最后一个有孩子的节点开始调整
    for(int i=n/2;i>=1;--i)
    {
        downAdjust(i,n);
    }

    //  堆排序
    HeapSort();
    /////insert(100);
     ////HeapSort();
    //deleteTop();
    //HeapSort();

    return 0;
}

具体例子

1.topK问题(找最大的k的元素--建小顶堆；最小的k个元素--建大顶堆)

class Solution {
public:
    // 优先级队列自定义数据类型的比较
    struct cmp{
        // 重写仿函数
        bool operator() (pair<int,int> a,pair<int,int> b)
        {
            return a.second>b.second; // 最小值优先
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int>mp;
        // 用map对每个出现的元素计数
        for(int i=0;i<nums.size();++i)
            mp[nums[i]]++;
        // 小顶堆
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>Q;
        for(auto item : mp)
        {
            // 如果堆内元素不足k个 则入堆
            if(Q.size()<k)
            {
                Q.push(item);
            }
            // 当前元素的频次低于堆顶元素 则不入堆
            else if(item.second>Q.top().second)
            {
                Q.pop();
                Q.push(item);
            }
        }
        vector<int>ans;
        while(!Q.empty())
        {
            ans.push_back(Q.top().first);
            Q.pop();
        }
        return ans;


    }
};

时间复杂度：O(nlogk） 空间复杂度:O(n)