堆是完全二叉树，我们使用下标从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();
}
}
参考文献：
