最大堆最小堆

自顶向下建堆

从根结点开始，然后一个一个的把结点插入堆中。当把一个新的结点插入堆中时，需要对结点进行调整，以保证插入结点后的堆依然是大根堆。
时间复杂度为$O(n\log_{2}{n})$

自底向上建堆

初始化建堆只需要对二叉树的非叶子节点调用Adjust()函数，由下至上，由右至左选取非叶子节点来调用Adjust()函数。那么倒数第二层的最右边的非叶子节点就是最后一个非叶子结点。

如果仅从下面展示的代码上直观观察，会得出构造二叉堆的时间复杂度为O(n)的结果，这个结果是错的，虽然该算法外层套一个n次循环，而内层套一个分治策略下的复杂度的循环，该思考方法犯了一个原则性错误，那就是构建二叉堆是自下而上的构建，每一层的最大纵深总是小于等于树的深度的，因此，该问题是叠加问题，而非递归问题。

假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；高层也是这样逐渐递归。

n个元素的完全二叉树，树高h为$log_{2}{(n+1)}$;

最下层非叶结点所需时间: $T(h-1) = 2^{(h-1)} * 1$;

第i层元素所需时间为$T(i) = 2^{i} * (h-i)$;

$$S = T(k-1) + T(k-2) +...+T(2) + T(1)$$

展开

$$S = 2^{(h-1)} * 1 + 2^{(h-2)} * 2+...+ 2 * (h-2) + (h-1)$$

求和公式为等差数列和等比数列的乘积

使用错位相减法可得

$$S = 2S-S = 2^{h}+2^{(h-1)} + ...+2 + 2*(h-1)= 2(2^{h} + h) - 1$$

将$h= log_{2}{(n+1)}$代入S

可得到$S=O(n)$

时间复杂度为$O(n)$

插入

时间复杂度:$O(\log_{2}{n})$

删除

时间复杂度:$O(\log_{2}{n})$

priority_queue

接口

• empty()
• size()
• push()
• top()
• pop()

声明方式

priority_queue<int> pq; //默认是最小堆
priority_queue<int,vector<int>,less<int>> pq; //最小堆
priority_queue<int,vector<int>,greater<int>> pq;//最大堆

//最大堆
class KthLargest {
    struct cmp{
        bool operator ()(int &x,int &y){
            return x>y;
        }
    };
private:
    int k;
    priority_queue<int,vector<int>,KthLargest::cmp> pq;
public:
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        int n = nums.size();
        for(int i = 0; i < n; i ++){
            if(pq.size()<k){pq.push(nums[i]);}
            else if(pq.top()<nums[i]){pq.pop();pq.push(nums[i]);}
        }
    }

    int add(int val) {
        if(pq.size()<this->k){pq.push(val);}
        else if(pq.top()<val){pq.pop();pq.push(val);}
        return pq.top();
    }
};

//最小堆
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        auto cmp=[](int a,int b){return a>b;};
        priority_queue<int,vector<int>,decltype(cmp)> pq(cmp);
        for(int i = 0; i < n; i ++){
            if(pq.size()<k){pq.push(nums[i]);}
            else if(pq.top()<nums[i]){pq.pop();pq.push(nums[i]);}
        }
        return pq.top();
    }
};