优先队列:小根堆

一、定义：
所有的父节点都小于子节点的完全二叉树。叫做小根堆。

二、性质：

1. 节点个数为N的小根堆，其高度为logN。
2. N/2之后的节点都是叶子结点。
3. 第i个节点的左儿子的序号是ix2,右儿子的序号是ix2+1，父亲节点的序号为i/2

三、如何存储?
用一维数组存储。申请一个长度为N+1的数组，

四、建堆的两种方式：

1. 直接用一个数组存储数，然后，从后往前依次调整数的位置，使以当前位置为根的二叉树为小根堆直到数组的第一个数。
2. 插入法，依次读入每个数，把它插入小根堆，并调整位置，使插入数后二叉树继续保持为小根堆

方式一代码 文末代码中create1方法
方式二代码 文末代码中create2方法

五、排序时间复杂度为 NlogN
文末代码中heapSort方法

六、从堆顶删除一个数?
文末代码中deleteMin方法

七、增加一个数?
文末代码中addOneNum方法

class SmallPriorityQueue {
    vector<int> h;
    int N;
public:
    
    SmallPriorityQueue(vector<int> & arr, int K) {
        N = K;
        h = arr;
        h.insert(h.begin(), 0);
    }
    
    void create1() {
        for(int i = N/2;i >= 1;i--) {
            shiftDown(i);
        }
    }
    
    void create2() {
        for(int i = 1;i <= N;i++) {
            shiftUp(i);
        }
    }
    
    int deleteMin() {
        int tmp = h[1];
        h[1] = h[N];
        N--;
        shiftDown(1);
        return tmp;
    }
    
    void addOneNum(int num) {
        N++;
        h.emplace_back(num);
        shiftUp(N);
    }
    
    vector<int> heapSort() {
        create1();
        vector<int> ans;
        while (N != 0) {
            int min = deleteMin();
            ans.emplace_back(min);
        }
        return ans;
    }
    
    void shiftDown(int i) {
        int t = 0;
        while (i * 2 <= N) {
            if (h[i*2] < h[i]) {
                t = i*2;
            }
            else {
                t = i;
            }
            if (i*2+1 <= N) {
                if (h[i*2+1] < h[t]) {
                    t = i*2+1;
                }
            }
            if (t != i) {
                swap(t, i);
                i = t;
            }
            else {
                break;
            }
        }
    }
    void shiftUp(int i) {
        if (i == 1) {
            return;
        }
        while (i != 1) {
            if (h[i/2] > h[i]) {
                swap(i/2, i);
                i /= 2;
            }
            else {
                break;
            }
        }
    }
    void swap(int x, int y) {
        int tmp = h[x];
        h[x] = h[y];
        h[y] = tmp;
    }
};