Java实现堆算法

堆是一种特殊的数据结构，它是一棵完全二叉树，且满足堆的性质：对于每个节点，它的值都不小于（或不大于）它的孩子节点的值。根节点的值就是堆中的最大值（或最小值）。

Java中提供了一个Heap类，可以用来实现堆的操作。Heap类是一个抽象类，它定义了堆的基本操作方法，如插入、删除、获取最大（或最小）值等。

要使用Heap类，需要创建一个具体的实现类，例如MaxHeap和MinHeap。这些类继承自Heap类，并实现了具体的插入、删除、获取最大（或最小）值等方法。下面我们以MaxHeap为例，来详细介绍如何实现堆。

MaxHeap的实现思路如下：

1. 定义一个数组来保存堆的元素，数组下标从1开始。

2. 定义一个变量来记录堆中元素的数量。

3. 实现插入方法：新元素插入到数组最后，然后使用上滤操作将新元素沿着路径向上移动，直到堆的性质被满足。

4. 实现删除方法：移除堆顶元素（数组下标为1的元素），然后将数组最后一个元素替换到堆顶，使用下滤操作将新元素沿着路径向下移动，直到堆的性质被满足。

5. 实现获取最大值方法：直接返回堆顶元素。

6. 实现堆排序方法：依次取出堆顶元素，将其放到一个新的数组中，然后重新调整堆。

以下是MaxHeap的代码实现：

public class MaxHeapextends Comparable> {
    private T[] heap; // 堆元素数组
    private int size; // 堆元素数量
 
    @SuppressWarnings("unchecked")
    public MaxHeap(int capacity) {
        heap = (T[]) new Comparable[capacity + 1]; // 数组下标从1开始
        size = 0;
    }
 
    public void insert(T value) {
        if (size == heap.length - 1) {
            resize();
        }
 
        heap[++size] = value; // 新元素插入到数组最后
        swim(size); // 上滤操作
    }
 
    public T deleteMax() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
 
        T max = heap[1]; // 堆顶元素
        heap[1] = heap[size--]; // 将数组最后一个元素替换到堆顶
        sink(1); // 下滤操作
        heap[size + 1] = null; // 释放旧的堆顶元素
 
        return max;
    }
 
    public T getMax() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
 
        return heap[1];
    }
 
    public void heapSort(T[] arr) {
        heapify(arr); // 初始化堆
        for (int i = size; i > 0; i--) {
            arr[i - 1] = deleteMax(); // 依次取出堆顶元素
        }
    }
 
    private void swim(int k) {
        while (k > 1 && heap[k].compareTo(heap[k / 2]) > 0) { // 父节点小于当前节点，上滤
            swap(k, k / 2);
            k /= 2; // 移动到父节点
        }
    }
 
    private void sink(int k) {
        while (2 * k <= size) { // 如果有左孩子
            int j = 2 * k;
            if (j < size && heap[j].compareTo(heap[j + 1]) < 0) { // 选择左右孩子中较大的那个
                j++;
            }
 
            if (heap[k].compareTo(heap[j]) >= 0) { // 如果父节点不小于孩子节点，下滤结束
                break;
            }
 
            swap(k, j); // 父节点和子节点交换
            k = j; // 移动到子节点
        }
    }
 
    private void heapify(T[] arr) {
        heap = (T[]) new Comparable[arr.length + 1];
        size = arr.length;
 
        System.arraycopy(arr, 0, heap, 1, arr.length); // 复制数组元素到堆中
 
        for (int i = size / 2; i >= 1; i--) { // 倒序下滤，从最后一个非叶子节点开始
            sink(i); // 下滤操作
        }
    }
 
    private void resize() {
        int newSize = heap.length * 2;
        heap = Arrays.copyOf(heap, newSize);
    }
 
    private void swap(int i, int j) {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

上面的代码实现了MaxHeap类，它支持插入、删除、获取最大值和堆排序等操作。堆排序的实现就是先将数组元素初始化成一个堆，然后依次取出堆顶元素，进行排序。

MaxHeap类中使用了泛型，可以存储任意类型的元素，只要实现了Comparable接口。使用时，可以像下面这样创建一个MaxHeap对象，然后调用其方法进行操作：

MaxHeap maxHeap = new MaxHeap<>(10);
maxHeap.insert(3);
maxHeap.insert(1);
maxHeap.insert(4);
maxHeap.insert(1);
maxHeap.insert(5);
System.out.println(maxHeap.deleteMax()); // 输出：5
System.out.println(maxHeap.getMax()); // 输出：4
 
Integer[] arr = {3, 1, 4, 1, 5};
maxHeap.heapSort(arr);
System.out.println(Arrays.toString(arr)); // 输出：[1, 1, 3, 4, 5]

总的来说，实现堆的关键在于实现上滤和下滤操作。上滤操作用于插入新元素时，将其从叶子节点沿着路径向上移动，下滤操作用于删除堆顶元素时，将最后一个元素从根节点沿着路径向下移动，维护堆的性质。堆排序的实现就是先将数组初始化成一个堆，然后依次取出堆顶元素，进行排序。最后，需要注意的是，在Java中实现堆可以使用Heap类，但也可以自己实现一个堆类，可以根据具体需求进行设计和优化。