2016 August 09

二叉堆

二叉堆是一棵完全二叉树，一般用数组来表示，且下标从1开始。

假设某个非根节点的下标为n(>1)，那么它的：

堆的性质

根据父子节点的大小关系，二叉堆可分为大根堆和小根堆。

二叉堆支持的操作有建堆、插入、弹出最值等，下面以大根堆为例分别说明。

建堆操作

建堆过程是调整现有数组的顺序，使之满足堆的性质。做法是从最后一个分支节点（下标为n/2）开始，到根节点为止，依次对每个分支节点做下沉操作，总时间复杂度为O(n)。

void down(int idx) {
    int i, j;
    for (i = idx; (j = 2*i) <= size; i = j) {
        if (j+1 <= size && h[j+1] > h[j])
            j += 1;
        if (h[j] <= h[i]) break;
        swap(h[i], h[j]);
    }
}
void heapify(int n) {
    size = n;
    for (int i = n/2; i >= 1; i--)
        down(i);
}

添加元素操作

先将元素放到最后，再上浮调整以满足堆的性质，时间复杂度为O(logn)。

void up(int idx) {
    while (idx > 1 && h[idx] > h[idx/2]; i /= 2)
        swap(h[i], h[i/2]);
}
void push(int val) {
    size += 1;
    h[size] = val;
    up(size);
}

弹出最值操作

二叉堆的最值在堆顶，即下标为1的位置。
弹出最值后，把最后的元素补到该处，对它做下沉操作，时间复杂度为O(logn)。

int top() {
    return h[1];
}
void pop() {
    h[1] = h[size];
    size -= 1;
    down(1);
}

判空操作

bool empty() {
    return size == 0;
}
Table of Contents