heap算法java

堆算法（Heap Algorithm）在Java中的实现与应用

堆的基本概念与性质

堆（Heap）是一种完全二叉树，分为最大堆（Max Heap）和最小堆（Min Heap），其核心性质如下：

堆的存储通常使用数组实现,父子节点的索引关系为：

• 父节点索引 i 的左子节点索引为 2i + 1
• 父节点索引 i 的右子节点索引为 2i + 2
• 子节点索引 j 的父节点索引为 (j-1)/2

这种存储方式保证了堆的高效访问，时间复杂度为 O(1)。

堆的核心操作

堆的核心操作包括插入（Insert）和删除（Delete），需维护堆的性质。

插入操作（以最大堆为例）

1. 将新元素添加到数组末尾。
2. 上浮（Sift Up）：比较新元素与其父节点，若违反最大堆性质，则交换位置，直到满足条件或到达根节点。

代码示例（Java）：

public void insert(int value) {
    array[size] = value; // 添加到末尾
    int current = size;
    size++;
    // 上浮操作
    while (current > 0) {
        int parent = (current 1) / 2;
        if (array[current] > array[parent]) {
            swap(current, parent);
            current = parent;
        } else {
            break;
        }
    }
}

删除操作（以最大堆为例）

1. 移除根节点（最大值），将最后一个元素移到根位置。
2. 下沉（Sift Down）：比较新根节点与其子节点，若违反最大堆性质，则与较大子节点交换，直到满足条件或成为叶子节点。

代码示例（Java）：

public int delete() {
    int max = array[0];
    array[0] = array[size 1]; // 用最后一个元素替换根
    size--;
    // 下沉操作
    int current = 0;
    while (current  2 + 1 < size) { // 非叶子节点
        int leftChild = current  2 + 1;
        int rightChild = current  2 + 2;
        int largerChild = leftChild;
        if (rightChild < size && array[rightChild] > array[leftChild]) {
            largerChild = rightChild;
        }
        if (array[current] < array[largerChild]) {
            swap(current, largerChild);
            current = largerChild;
        } else {
            break;
        }
    }
    return max;
}

堆排序（Heap Sort）

堆排序利用堆的特性实现升序排序,步骤如下：

1. 将待排序数组构建成最大堆。
2. 反复移除堆顶元素（当前最大值），并将其放到数组末尾，调整剩余堆。
3. 最终得到升序数组。

时间复杂度：O(n log n)（构建堆 O(n)，每次删除 O(log n)）。

代码示例（Java）：

public void heapSort(int[] arr) {
    int n = arr.length;
    // 构建最大堆
    for (int i = n / 2 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }
    // 逐个提取元素
    for (int i = n 1; i > 0; i--) {
        swap(arr, 0, i); // 将堆顶元素移到末尾
        siftDown(arr, i, 0); // 调整剩余堆
    }
}
private void siftDown(int[] arr, int n, int i) {
    int largest = i;
    int left = 2  i + 1;
    int right = 2  i + 2;
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(arr, i, largest);
        siftDown(arr, n, largest);
    }
}

Java中的PriorityQueue实现堆

Java标准库提供了PriorityQueue，默认是最小堆，可通过自定义Comparator实现最大堆。

示例：自定义最大堆

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(5); // 添加元素
maxHeap.offer(10);
int max = maxHeap.poll(); // 获取并移除堆顶元素（最大值）

自定义堆的完整实现（Java）

以下是一个支持动态扩容的最小堆实现：

public class MinHeap {
    private int[] heap;
    private int size;
    private static final int CAPACITY = 10;
    public MinHeap() {
        heap = new int[CAPACITY];
        size = 0;
    }
    public void insert(int value) {
        if (size == heap.length) {
            resize();
        }
        heap[size] = value;
        int current = size;
        size++;
        // 上浮操作
        while (current > 0) {
            int parent = (current 1) / 2;
            if (heap[current] < heap[parent]) {
                swap(current, parent);
                current = parent;
            } else {
                break;
            }
        }
    }
    public int remove() {
        if (size == 0) throw new IllegalStateException("Heap is empty");
        int min = heap[0];
        heap[0] = heap[size 1];
        size--;
        // 下沉操作
        int current = 0;
        while (current  2 + 1 < size) {
            int leftChild = current  2 + 1;
            int rightChild = current  2 + 2;
            int smallerChild = leftChild;
            if (rightChild < size && heap[rightChild] < heap[leftChild]) {
                smallerChild = rightChild;
            }
            if (heap[current] > heap[smallerChild]) {
                swap(current, smallerChild);
                current = smallerChild;
            } else {
                break;
            }
        }
        return min;
    }
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
    private void resize() {
        int[] newHeap = new int[heap.length  2];
        System.arraycopy(heap, 0, newHeap, 0, heap.length);
        heap = newHeap;
    }
}

FAQs（常见问题解答）

Q1：堆排序是否稳定？为什么？

A1：堆排序是不稳定的，因为在调整堆的过程中，可能会交换相等元素的相对位置，当两个相等元素分别位于左右子树时，下沉操作可能破坏它们的原始顺序。

Q2：堆的常见应用场景有哪些？

A2：堆的应用场景包括：

1. 优先队列：快速获取最大或最小元素（如任务调度、事件处理）。
2. 拓扑排序：用于有向无环图的排序。
3. 中位数查找：使用两个堆（大顶堆和小顶堆）动态维护数据流的中位数。
4. 合并多路有序数组：利用最小堆合并