模拟堆

一、底层实现

完全二叉树：除最后一层是从左到右排列，其余层数都是满的。

小根堆：每一层的父节点一定小于等于左右子节点，根节点为最小值。

二、存储

手写堆的完全二叉树是用一个一维数组存储：

根节点：1， 左节点：2x， 右节点：2x + 1

三、建堆

暴力建堆 O(nlogn)

for(int i=n; i; i--) down(i); // 逆遍历的原因是：down操作必须满足有左右子节点

优化建堆 O(n)

for(int i=n/2; i; i--) down(i); // 优化原因：

四、操作

1.插入一个数：$$heap[++size] = x, up(size);$$

2.求集合当中最小值：$$heap[1];$$

3.删除最小值：$$heap[1] = heap[size], size- -, down(1);$$

4.删除任意一个元素：$$heap[k] = heap[size], size- -, down(k), up(k);$$

5.修改任意一个元素：$$heap[k] = x, down(k), up(k);$$

五、函数实现

down函数

void down(int u)
{
    int max_i = u; // max_v表示父节点和两个子节点中最小值的下标
    if(u * 2 <= cnt && h[u * 2] < h[max_i]) max_i = u * 2;
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[max_i]) max_i = u * 2 + 1;
    if(max_i != u)
    {
        swap(h[max_i], h[u]);
        down(max_i);
    }
}

up函数

void up(int u)
{
    while(u / 2 && h[u / 2] > h[u])
    {
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}