跳到主要内容

堆

堆的性质​

  1. 堆中某个节点的值总是不大于或不小于其父节点的值；
  2. 堆总是一棵完全二叉树。
  3. 最后一个非叶结点是第n/2个结点。这里建堆的时候会用到，复杂度可以降到O(n)；
  4. 如果一个点为u，那么它的左儿子为2*u，右儿子为2*u+1
  5. 对于小根堆来讲，每个以u为根节点的树，它的左右儿子的值一定大于父节点。所以对堆进行建立的时候，如果当前点与它的左右儿子并不满足这一性质，就需要进行交换。
  • 小根堆：子节点比父节点大
  • 大根堆：子节点比父节点小

建堆的过程：

从n/2开始，到1即可，

代码​

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

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

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
0%