二叉堆

堆是完全二叉树，我们使用下标从1开始的数组来表示这颗树，1代表根节点，对于每个节点，它的左孩子为，右孩子为，父亲节点为。最大堆和最小堆是二叉堆的形式，按照最大元素位于根节点排列的二叉堆被称为最大堆，同理按照最小元素位于根节点排列的二叉堆被称为最小堆。

二叉堆中主要的操作有查询、删除、插入，对于破坏堆性质的节点，可以使用上浮和下沉操作进行调整。

下面的操作以最大堆为例。

上浮

不断与父节点比较，如果比父节点大就与之交换，直到不大于父节点或成为根节点为止。

void up(int p) {
    for (int i = p; i > 1 && heap[i] > heap[i / 2]; i = i / 2) {
        swap(i, i / 2);
    }
}

void swap(int p1, int p2) {
    heap[p1] += heap[p2];
    heap[p2] = heap[p1] - heap[p2];
    heap[p1] = heap[p1] - heap[p2];
}

下沉

不断与较大的子节点比较，如果比它小就与之交换，直到不小于任何子节点或成为叶子节点为止。

void down(int p) {
    for (int i = p, j = son(i); j < heap.length && heap[j] > heap[i]; i = j, j = son(i)) {
        swap(i, j);
    }
}

int son(int p) {
    return 2 * p + ((2 * p + 1 <= heap.length && heap[2 * p + 1] > heap[p]) ? 1 : 0);
}

插入

直接在数组尾部插入值，然后上浮即可。

void push(int v) {
    heap[++size] = v;
    up(size);
}

删除

可以将根节点与最后一个节点交换，使size减1，然后根节点下沉。

void pop() {
    swap(1, size--);
    down(1);
}

查询

直接返回根节点即可。

int top() {
    return heap[1];
}

代码

完整的代码为：

public class Template {

    int size;
    int[] heap;

    public Template(int _size) {
        heap = new int[_size + 1];
        size = 0;
    }

    void up(int p) {
        for (int i = p; i > 1 && heap[i] > heap[i / 2]; i = i / 2) {
            swap(i, i / 2);
        }
    }

    void swap(int p1, int p2) {
        heap[p1] += heap[p2];
        heap[p2] = heap[p1] - heap[p2];
        heap[p1] = heap[p1] - heap[p2];
    }

    void down(int p) {
        for (int i = p, j = son(i); j < size && heap[j] > heap[i]; i = j, j = son(i)) {
            swap(i, j);
        }
    }

    int son(int p) {
        return 2 * p + ((2 * p + 1 <= size && heap[2 * p + 1] > heap[p]) ? 1 : 0);
    }

    void push(int v) {
        if (size >= heap.length - 1) return;
        heap[++size] = v;
        up(size);
    }

    void pop() {
        if (size > 0) return;
        swap(1, size--);
        down(1);
    }

    int top() {
        return heap[1];
    }

    public static void main(String[] args) {
        Template template = new Template(2);
        template.push(2);
        template.push(5);
        template.pop();
        template.pop();
    }
}

参考文献：

1. 算法学习笔记(47): 二叉堆