数据结构第17节 最小堆

最小堆（Min Heap）是一种特殊的完全二叉树数据结构，在这种结构中，对于任意节点，其值都小于或等于它的子节点的值。根节点是堆中的最小元素。最小堆常用于实现优先队列，以及堆排序算法。

在Java中，我们可以使用数组或ArrayList来实现最小堆，因为完全二叉树的特性允许我们通过简单的数学运算在数组中找到父节点和子节点的位置。

最小堆的基本操作：

1. 插入元素：将新元素添加到数组的末尾，然后从下至上调整以保持最小堆的性质。
2. 删除最小元素：移除数组的第一个元素（即堆顶），然后将最后一个元素移到堆顶，再从上至下调整以保持堆的性质。
3. 获取最小元素：直接访问数组的第一个元素。

示例代码：

下面是一个简单的Java实现最小堆的示例：

import java.util.Arrays;

public class MinHeap {
    private int[] heap;
    private int size;

    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    // 插入元素
    public void insert(int value) {
        if (size == heap.length) {
            throw new IllegalStateException("Heap is full");
        }
        heap[size] = value;
        siftUp(size);
        size++;
    }

    // 上浮操作，保持最小堆性质
    private void siftUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[parentIndex] > heap[index]) {
                swap(parentIndex, index);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    // 删除并返回最小元素
    public int extractMin() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        siftDown(0);
        return min;
    }

    // 下沉操作，保持最小堆性质
    private void siftDown(int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int smallest = index;

        if (leftChildIndex < size && heap[leftChildIndex] < heap[smallest]) {
            smallest = leftChildIndex;
        }
        if (rightChildIndex < size && heap[rightChildIndex] < heap[smallest]) {
            smallest = rightChildIndex;
        }
        if (smallest != index) {
            swap(index, smallest);
            siftDown(smallest);
        }
    }

    // 交换两个元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 打印堆的内容
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        MinHeap heap = new MinHeap(10);
        heap.insert(10);
        heap.insert(1);
        heap.insert(15);
        heap.insert(5);
        heap.printHeap(); // 输出: [1, 5, 10, 15]
        System.out.println("Extracted min: " + heap.extractMin()); // 输出: Extracted min: 1
        heap.printHeap(); // 输出: [5, 10, 15]
    }
}

这段代码创建了一个最小堆，并提供了插入和删除最小元素的功能。注意，实际应用中可能需要处理堆满或空的情况，以及可能的异常情况。此外，上述代码未包含容量自动扩展的逻辑，实际使用时应考虑这一点。

为了使代码更加健壮和实用，我们可以添加以下功能：

1. 自动扩展堆的容量：当插入元素导致堆溢出时，动态地增加堆的大小。
2. 堆的初始化：提供一个构造函数接受一个数组，可以立即构建一个最小堆。
3. 获取堆的大小和是否为空的方法。

以下是完善后的代码：

import java.util.Arrays;

public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity];
        size = 0;
    }

    // 构造函数，接收一个数组，构建最小堆
    public MinHeap(int[] arr) {
        this(arr.length);
        for (int value : arr) {
            insert(value);
        }
    }

    public void insert(int value) {
        ensureCapacity();
        heap[size] = value;
        siftUp(size);
        size++;
    }

    private void ensureCapacity() {
        if (size == heap.length) {
            int newCapacity = heap.length * 2;
            heap = Arrays.copyOf(heap, newCapacity);
            capacity = newCapacity;
        }
    }

    public int extractMin() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        siftDown(0);
        return min;
    }

    private void siftUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[parentIndex] > heap[index]) {
                swap(parentIndex, index);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    private void siftDown(int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int smallest = index;

        if (leftChildIndex < size && heap[leftChildIndex] < heap[smallest]) {
            smallest = leftChildIndex;
        }
        if (rightChildIndex < size && heap[rightChildIndex] < heap[smallest]) {
            smallest = rightChildIndex;
        }
        if (smallest != index) {
            swap(index, smallest);
            siftDown(smallest);
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 1, 15, 5};
        MinHeap heap = new MinHeap(arr);

        System.out.println("Initial heap:");
        heap.printHeap();

        System.out.println("\nExtracted min: " + heap.extractMin());
        System.out.println("Heap after extraction:");
        heap.printHeap();

        System.out.println("\nInserting 3:");
        heap.insert(3);
        heap.printHeap();
        
        System.out.println("\nHeap size: " + heap.getSize());
        System.out.println("Is heap empty? " + heap.isEmpty());
    }
}

这个版本的最小堆类现在可以处理动态容量扩展，初始化一个已有元素的堆，以及提供了一些额外的辅助方法。

让我们通过一个表格逐步演示如何使用上面定义的 MinHeap 类。我们将执行一系列操作，包括插入元素、提取最小元素、检查堆的状态等。

初始状态

操作 1: 插入元素 10

操作 2: 插入元素 1

操作 3: 插入元素 15

操作 4: 插入元素 5

操作 5: 提取最小元素

提取后，堆中最小元素（1）被删除，最后一个元素（15）被移动到堆顶，并进行下沉操作以保持堆的性质。

进行下沉操作后：

操作 6: 插入元素 3

操作 7: 检查堆的大小和是否为空

• 堆的大小: 4
• 堆是否为空: false

通过这个步骤，我们可以清楚地看到 MinHeap 类是如何管理元素的插入、删除和维护堆的性质的。