Java 数据结构与算法系列精讲之二叉堆

什么是二叉堆？

二叉堆是一种基于完全二叉树的数据结构，它分为大根堆（MaxHeap）和小根堆（MinHeap）。大根堆的每个节点的值都大于（或等于）它的子节点的值，小根堆的每个节点的值都小于（或等于）它的子节点的值。

二叉堆的操作

二叉堆主要有以下几种操作：

1. 插入元素：将元素插入到堆的最后一个叶子节点，然后通过上滤操作使其满足堆的性质。
2. 删除元素：将堆的根节点删除，并将最后一个叶子节点移动到根节点，然后通过下滤操作使其满足堆的性质。
3. 大小比较：将堆的根节点与另一个元素进行大小比较。

示例一、插入元素

public void insert(int x) {
    if (size == capacity) {//如果已经满了
        throw new RuntimeException("Heap is full");
    }
    heap[size++] = x;
    siftUp(size - 1);//上滤
}

在插入元素的过程中，我们首先需要判断堆是否已满，如果堆已满，则抛出异常。如果堆未满，则将元素插入到堆的最后一个叶子节点，然后通过上滤操作使其满足堆的性质。

示例二、删除元素

public int deleteMax() {
    if (size == 0) {//如果堆为空
        throw new RuntimeException("Heap is empty");
    }
    int max = heap[0];//取出根节点
    heap[0] = heap[size-1];//将最后一个叶子节点移动到根节点
    size--;//堆大小减一
    siftDown(0);//下滤
    return max;//返回被删除的根节点
}

在删除元素的过程中，我们首先需要判断堆是否为空，如果为空则抛出异常。否则，我们可以将堆的根节点删除，并将最后一个叶子节点移动到根节点，然后通过下滤操作使其满足堆的性质。

适用场景

1. 堆排序：通过维护一个大根堆实现排序。
2. TopK 问题：维护一个小根堆，当堆的大小等于 K 时，堆的根节点即为前 K 大的元素。
3. 求中位数：维护一个大根堆和一个小根堆，大根堆存储较小的一半元素，小根堆存储较大的一半元素。

总结

二叉堆是一种非常常用的数据结构，它是堆排序、TopK 问题和求中位数等问题的核心数据结构。我们需要掌握二叉堆的基本操作，以便于解决各种实际问题。