当前位置：首页 > Java

java 如何表示堆

2026-03-22 18:03:42Java

堆的基本概念

堆是一种特殊的完全二叉树，分为最大堆和最小堆。最大堆中父节点的值大于或等于子节点的值，最小堆中父节点的值小于或等于子节点的值。堆常用于优先队列和堆排序等场景。

使用数组表示堆

堆通常用数组实现，利用完全二叉树的性质可以高效地通过索引访问父节点和子节点。对于数组中索引为i的节点：

java 如何表示堆

父节点索引：(i - 1) / 2
左子节点索引：2 * i + 1
右子节点索引：2 * i + 2

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

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

堆的基本操作

插入元素 将新元素添加到堆的末尾，然后通过“上浮”操作调整堆结构：

public void insert(int value) {
    if (size == capacity) {
        throw new IllegalStateException("Heap is full");
    }
    heap[size] = value;
    heapifyUp(size);
    size++;
}

private void heapifyUp(int index) {
    int parent = (index - 1) / 2;
    while (index > 0 && heap[index] > heap[parent]) {
        swap(index, parent);
        index = parent;
        parent = (index - 1) / 2;
    }
}

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

删除堆顶元素 将堆顶元素与末尾元素交换，移除末尾元素后通过“下沉”操作调整堆结构：

java 如何表示堆

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

private void heapifyDown(int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int largest = index;

    if (left < size && heap[left] > heap[largest]) {
        largest = left;
    }
    if (right < size && heap[right] > heap[largest]) {
        largest = right;
    }
    if (largest != index) {
        swap(index, largest);
        heapifyDown(largest);
    }
}

使用优先队列实现堆

Java的PriorityQueue类默认实现最小堆，可通过自定义比较器实现最大堆：

// 最小堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

堆的应用示例

堆排序 利用堆的性质实现排序：

public void heapSort(int[] arr) {
    int n = arr.length;
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    // 逐个提取元素
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

private void heapify(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);
        heapify(arr, n, largest);
    }
}