手写数据结构：堆|睡懒觉的随想录

堆是一种满足特定条件的完全二叉树，可以分为两种：

最小堆：任意节点的值 \le 其子节点的值。
最大堆：任意节点的值 \ge 其子节点的值。

一、堆的实现

1.1 堆存储与表示

完全二叉树非常适合用数组表示给定索引 i，左子节点的索引为 2i+1，右子节点的索引为 2i+2，父节点的索引为 (i-1)/2，索引越界表示节点不存在。注：索引从 0 开始，到 n-1 结束。

// 数组实现堆
List<Integer> maxHeap = new ArrayList<>();

// 获取左子节点的索引
public int left(int i) {
    return 2 * i + 1;
}

// 获取右子节点的索引
public int right(int i) {
    return 2 * i + 2;
}

// 获取父节点的索引
public int parent(int i) {
    return (i - 1) / 2;
}

1.2 访问堆顶元素

根节点就是堆顶元素，最大/小堆的堆顶元素是最大/小的元素。

// 访问堆顶元素
public int peek(){
    return maxHeap.getFirst();
}

1.3 元素入堆

给定元素 x，首先将其插入堆尾，然后自底向上维护堆的性质。

// 元素如堆
public void push(int x) {
    // 在堆尾插入元素
    maxHeap.add(x);
    // 自底向上堆化
    siftUp(maxHeap.size() - 1);
}

// 从节点 i 开始，自底向上堆化
public void siftUp(int i) {
    // 获取父节点
    int p = parent(i);
    // 当“越过根节点”或“节点无须修复”时，结束堆化
    if (p < 0 || maxHeap.get(p) >= maxHeap.get(i)) {
        return;
    }
    swap(i, p); // 交换两个节点
    siftUp(p);  // 递归向上堆化
}

// 交换两个元素
public void swap(int i, int j) {
    int tmp = maxHeap.get(i);
    maxHeap.set(i, maxHeap.get(j));
    maxHeap.set(j, tmp);
}

1.4 元素出堆

堆顶元素是二叉树的根节点，如果直接删除首元素，二叉树中所有节点的索引发生变化，会为维护堆的性质带来麻烦。因此，堆顶元素出堆可以通过下面的步骤实现：

交换堆顶元素与堆底元素
删除堆底元素
从根节点开始，自顶向下堆化

// 判断堆是否为空
public boolean isEmpty(){
    return maxHeap.isEmpty();
}

// 堆顶元素出堆
public int pop(){
    // 判空处理
    if (isEmpty()){
        throw new IndexOutOfBoundsException();
    }
    // 交换堆顶元素和堆底元素
    swap(0, maxHeap.size() - 1);
    // 删除堆底元素
    int val = maxHeap.removeLast();
    // 自顶向下堆化
    siftDown(0);
    return val;
}

public void siftDown(int i){
    int l = left(i);
    int r = right(i);
    int mx = i; // 判断节点 i, l, r 中值最大的节点，记为 mx
    if (l < maxHeap.size() && maxHeap.get(l) > maxHeap.get(mx)){
        mx = l;
    }
    if (r < maxHeap.size() && maxHeap.get(r) > maxHeap.get(mx)){
        mx = r;
    }
    // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
    if (mx == i){
        return;
    }
    swap(i, mx);    // 交换两个节点
    siftDown(mx);   // 继续向下堆化
}

1.5 建堆操作

一种高效的建堆操作：

将列表中所有元素原封不动的添加到堆中；
倒序遍历数组，堆每个非叶子节点执行「自顶向下堆化」。

每当堆化一个节点后，以该节点为根节点的子树就形成一个合法的子堆。由于叶节点没有子节点，因此它们天然就是合法的子堆，无须堆化。

// 原地堆化
public void heapify(List<Integer> nums) {
    maxHeap = new ArrayList<>(nums);
    // 堆化除叶节点以外的其他所有节点
    for (int i = parent(maxHeap.size() - 1); i >= 0; i--) {
        siftDown(i);
    }
}