二叉堆详解

本文最后更新于：1 天前

二叉堆（Binary Heap）技术详解

目录

  1. 二叉堆的性质
  2. 最常见的应用：优先级队列
  3. 另一种应用：堆排序

一、二叉堆的性质

1.1 基本定义

二叉堆（Binary Heap）是一种特殊的完全二叉树数据结构，满足堆性质（Heap Property）。它是实现优先级队列和堆排序算法的基础。

核心特征：

  • 完全二叉树结构：所有层级都被填满，除了最后一层，且最后一层的节点从左到右填充
  • 堆性质：每个节点的值与其子节点保持特定的大小关系
  • 数组表示：可以高效地使用数组存储，无需指针

1.2 堆的两种类型

Min Heap and Max Heap

类型 定义 根节点特性
最小堆（Min Heap） 父节点的值 ≤ 子节点的值 根节点为最小值
最大堆（Max Heap） 父节点的值 ≥ 子节点的值 根节点为最大值

1.3 数组索引关系

二叉堆通常使用数组进行层级遍历（Level Order）存储。对于索引为 i 的节点(数组索引从0开始)：

Array Representation

  • 父节点索引：parent(i) = floor((i - 1) / 2)
  • 左子节点索引：left(i) = 2 * i + 1
  • 右子节点索引：right(i) = 2 * i + 2

示例：

1
2
3
4
5
6
7
8
数组表示：[5, 10, 20, 17, 6, 22, 26]

索引：    0   1   2   3   4   5   6
         5
       /   \
     10     20
    / \     / \
   17  6   22  26

1.4 关键性质总结

  1. 高度性质：含有 n 个节点的二叉堆高度为 ⌊log₂n⌋
  2. 时间复杂度：
    • 查询最值：O(1)
    • 插入操作：O(log n)
    • 删除操作：O(log n)
  3. 空间复杂度：O(n)，使用数组紧凑存储

1.5 基础Java实现（最大堆）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/**
 * 最大堆（Max Heap）基础实现
 * 演示二叉堆的核心操作：上浮（Heapify Up）和下沉（Heapify Down）
 */
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];
    }

    // 获取父节点索引
    private int parent(int i) {
        return (i - 1) / 2;
    }

    // 获取左子节点索引
    private int leftChild(int i) {
        return 2 * i + 1;
    }

    // 获取右子节点索引
    private int rightChild(int i) {
        return 2 * i + 2;
    }

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

    /**
     * 上浮操作（Heapify Up / Bubble Up）
     * 用于插入新元素后恢复堆性质
     * 时间复杂度：O(log n)
     */
    private void heapifyUp(int index) {
        while (index > 0 && heap[parent(index)] < heap[index]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    /**
     * 下沉操作（Heapify Down / Bubble Down）
     * 用于删除堆顶后恢复堆性质
     * 时间复杂度：O(log n)
     */
    private void heapifyDown(int index) {
        int maxIndex = index;
        int left = leftChild(index);
        int right = rightChild(index);

        // 与左子节点比较
        if (left < size && heap[left] > heap[maxIndex]) {
            maxIndex = left;
        }

        // 与右子节点比较
        if (right < size && heap[right] > heap[maxIndex]) {
            maxIndex = right;
        }

        // 如果当前节点不是最大值，交换并继续下沉
        if (index != maxIndex) {
            swap(index, maxIndex);
            heapifyDown(maxIndex);
        }
    }

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

    // 提取最大值（删除堆顶）
    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;
    }

    // 查看最大值
    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        return heap[0];
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(3);
        maxHeap.insert(1);
        maxHeap.insert(4);
        maxHeap.insert(1);
        maxHeap.insert(5);
        maxHeap.insert(9);
        maxHeap.insert(2);
        maxHeap.insert(6);

        System.out.println("Max value: " + maxHeap.peek()); // 输出: 9
        
        while (maxHeap.size > 0) {
            System.out.print(maxHeap.extractMax() + " ");
        }
        // 输出: 9 6 5 4 3 2 1 1
    }
}

二、最常见的应用：优先级队列

2.1 概念说明

优先级队列（Priority Queue） 是一种抽象数据类型，其中每个元素都有关联的优先级。与FIFO（先进先出）的普通队列不同，优先级队列总是先处理优先级最高的元素。

二叉堆实现的优势：

  • 插入和删除操作均为 O(log n)
  • 查看最高优先级元素为 O(1)
  • 空间效率高，实现简洁

2.2 堆操作示意图

Heap Operations

上图展示了堆的核心操作：

  1. 插入（Insert）：新元素添加到末尾，然后上浮
  2. 删除最大值（Remove the Maximum）：交换堆顶与末尾，删除末尾，然后下沉

2.3 完整Java实现（泛型优先级队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 基于最大堆的泛型优先级队列实现
 * 支持自定义比较器，可作为最大堆或最小堆使用
 */
public class PriorityQueue<T extends Comparable<T>> {
    private List<T> heap;
    private Comparator<T> comparator;
    private boolean isMaxHeap;

    /**
     * 默认构造：最大堆
     */
    public PriorityQueue() {
        this(true);
    }

    /**
     * 指定堆类型构造
     * @param isMaxHeap true为最大堆，false为最小堆
     */
    public PriorityQueue(boolean isMaxHeap) {
        this.heap = new ArrayList<>();
        this.isMaxHeap = isMaxHeap;
        this.comparator = isMaxHeap ? Comparator.reverseOrder() : Comparator.naturalOrder();
    }

    /**
     * 使用自定义比较器构造
     */
    public PriorityQueue(Comparator<T> comparator) {
        this.heap = new ArrayList<>();
        this.comparator = comparator;
        this.isMaxHeap = false; // 由比较器决定
    }

    // 获取父节点索引
    private int parent(int i) {
        return (i - 1) / 2;
    }

    // 获取左子节点索引
    private int leftChild(int i) {
        return 2 * i + 1;
    }

    // 获取右子节点索引
    private int rightChild(int i) {
        return 2 * i + 2;
    }

    /**
     * 上浮操作（Heapify Up）
     * 插入后调整堆结构
     */
    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIdx = parent(index);
            // 如果是最大堆，当前节点大于父节点则交换；最小堆则相反
            if (comparator.compare(heap.get(index), heap.get(parentIdx)) > 0) {
                swap(index, parentIdx);
                index = parentIdx;
            } else {
                break;
            }
        }
    }

    /**
     * 下沉操作（Heapify Down）
     * 删除堆顶后调整堆结构
     */
    private void heapifyDown(int index) {
        int size = heap.size();
        while (true) {
            int leftIdx = leftChild(index);
            int rightIdx = rightChild(index);
            int priorityIdx = index;

            // 与左子节点比较
            if (leftIdx < size && 
                comparator.compare(heap.get(leftIdx), heap.get(priorityIdx)) > 0) {
                priorityIdx = leftIdx;
            }

            // 与右子节点比较
            if (rightIdx < size && 
                comparator.compare(heap.get(rightIdx), heap.get(priorityIdx)) > 0) {
                priorityIdx = rightIdx;
            }

            // 如果当前节点已经是优先级最高的，停止
            if (priorityIdx == index) {
                break;
            }

            swap(index, priorityIdx);
            index = priorityIdx;
        }
    }

    private void swap(int i, int j) {
        T temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    /**
     * 入队操作（Enqueue）
     * 时间复杂度：O(log n)
     */
    public void enqueue(T item) {
        heap.add(item);
        heapifyUp(heap.size() - 1);
    }

    /**
     * 出队操作（Dequeue）
     * 移除并返回优先级最高的元素
     * 时间复杂度：O(log n)
     */
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Priority queue is empty");
        }

        T frontItem = heap.get(0);
        int lastIdx = heap.size() - 1;

        // 将最后一个元素移到堆顶
        heap.set(0, heap.get(lastIdx));
        heap.remove(lastIdx);

        // 如果堆不为空，执行下沉操作
        if (!isEmpty()) {
            heapifyDown(0);
        }

        return frontItem;
    }

    /**
     * 查看队首元素（不移除）
     * 时间复杂度：O(1)
     */
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Priority queue is empty");
        }
        return heap.get(0);
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }

    public int size() {
        return heap.size();
    }

    /**
     * 使用示例：任务调度系统
     */
    public static void main(String[] args) {
        // 示例1：整数最大堆（默认）
        System.out.println("=== 最大堆示例 ===");
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>();
        maxPQ.enqueue(5);
        maxPQ.enqueue(1);
        maxPQ.enqueue(3);
        maxPQ.enqueue(2);
        maxPQ.enqueue(4);
        
        System.out.print("出队顺序（从高到低）: ");
        while (!maxPQ.isEmpty()) {
            System.out.print(maxPQ.dequeue() + " ");
        }
        // 输出: 5 4 3 2 1

        // 示例2：整数最小堆
        System.out.println("\n=== 最小堆示例 ===");
        PriorityQueue<Integer> minPQ = new PriorityQueue<>(false);
        minPQ.enqueue(5);
        minPQ.enqueue(1);
        minPQ.enqueue(3);
        minPQ.enqueue(2);
        minPQ.enqueue(4);
        
        System.out.print("出队顺序（从低到高）: ");
        while (!minPQ.isEmpty()) {
            System.out.print(minPQ.dequeue() + " ");
        }
        // 输出: 1 2 3 4 5

        // 示例3：自定义对象（任务调度）
        System.out.println("\n=== 任务调度示例 ===");
        class Task {
            String name;
            int priority; // 数字越大优先级越高
            
            Task(String name, int priority) {
                this.name = name;
                this.priority = priority;
            }
            
            @Override
            public String toString() {
                return name + "(P" + priority + ")";
            }
        }

        PriorityQueue<Task> taskQueue = new PriorityQueue<>(
            Comparator.comparingInt((Task t) -> t.priority).reversed()
        );
        
        taskQueue.enqueue(new Task("普通邮件", 1));
        taskQueue.enqueue(new Task("紧急Bug", 5));
        taskQueue.enqueue(new Task("代码审查", 2));
        taskQueue.enqueue(new Task("系统宕机", 10));
        taskQueue.enqueue(new Task("文档更新", 1));

        System.out.println("任务处理顺序:");
        while (!taskQueue.isEmpty()) {
            System.out.println("处理: " + taskQueue.dequeue());
        }
        // 输出顺序: 系统宕机 -> 紧急Bug -> 代码审查 -> 普通邮件/文档更新
    }
}

2.4 使用Java标准库PriorityQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.PriorityQueue;
import java.util.Comparator;

/**
 * Java标准库PriorityQueue使用示例
 * 默认是最小堆，可通过Comparator改为最大堆
 */
public class StandardPriorityQueueDemo {
    public static void main(String[] args) {
        // 默认最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(5);
        minHeap.offer(1);
        minHeap.offer(3);
        System.out.println("Min Heap Peek: " + minHeap.peek()); // 1

        // 最大堆（使用Comparator）
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.offer(5);
        maxHeap.offer(1);
        maxHeap.offer(3);
        System.out.println("Max Heap Peek: " + maxHeap.peek()); // 5

        // 自定义对象示例
        PriorityQueue<String> stringPQ = new PriorityQueue<>(
            Comparator.comparingInt(String::length).reversed()
        );
        stringPQ.offer("Hi");
        stringPQ.offer("Hello");
        stringPQ.offer("Hey");
        
        System.out.println("最长字符串: " + stringPQ.poll()); // Hello
    }
}

三、另一种应用：堆排序

3.1 算法原理

堆排序（Heap Sort） 是一种基于二叉堆的比较排序算法，由J. W. J. Williams在1964年发明。其核心思想是利用堆的性质进行排序：

算法步骤：

  1. 建堆（Heapify）：将无序数组构建成最大堆，时间复杂度 O(n)
  2. 排序阶段：重复将堆顶（最大值）与末尾元素交换，然后对剩余元素重新堆化
  3. 最终数组呈现升序排列

3.2 堆排序过程可视化

Heap Sort Process

上图展示了堆排序的完整过程：

  • Step 1-2：初始数组构建最大堆
  • Step 3-10：每次将最大值移到数组末尾，并对剩余部分重新堆化

3.3 完整Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
import java.util.Arrays;

/**
 * 堆排序（Heap Sort）完整实现
 * 时间复杂度：O(n log n)
 * 空间复杂度：O(1) - 原地排序
 * 不稳定排序
 */
public class HeapSort {
    
    /**
     * 堆排序主方法
     * 步骤：
     * 1. 构建最大堆（Build Max Heap）
     * 2. 逐个提取最大值并放到数组末尾
     */
    public static void heapSort(int[] arr) {
        int n = arr.length;
        
        // 步骤1：构建最大堆
        // 从最后一个非叶子节点开始（n/2 - 1），向上调整
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // 步骤2：排序
        // 逐个将堆顶（最大值）移到数组末尾
        for (int i = n - 1; i > 0; i--) {
            // 将当前根（最大值）与末尾元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            // 对缩减后的堆（0到i-1）重新堆化
            heapify(arr, i, 0);
        }
    }
    
    /**
     * 堆化方法（Heapify）
     * 将以i为根的子树调整为最大堆
     * 
     * @param arr 数组
     * @param n 堆的大小（数组有效长度）
     * @param i 当前根节点索引
     */
    private static 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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            
            // 递归调整受影响的子树
            heapify(arr, n, largest);
        }
    }
    
    /**
     * 打印数组
     */
    private static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
    
    /**
     * 使用Java PriorityQueue实现的堆排序（简单版）
     * 时间复杂度相同，但空间复杂度为O(n)
     */
    public static void heapSortUsingPQ(int[] arr) {
        java.util.PriorityQueue<Integer> pq = 
            new java.util.PriorityQueue<>(java.util.Collections.reverseOrder());
        
        // 入队
        for (int num : arr) {
            pq.offer(num);
        }
        
        // 出队到数组（从后往前填充，实现升序）
        for (int i = arr.length - 1; i >= 0; i--) {
            arr[i] = pq.poll();
        }
    }
    
    /**
     * 详细演示版本：展示每一步的变化
     */
    public static void heapSortWithTrace(int[] arr) {
        int n = arr.length;
        System.out.println("初始数组: " + Arrays.toString(arr));
        
        // 建堆阶段
        System.out.println("\n=== 建堆阶段 ===");
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
            System.out.println("堆化索引 " + i + " 后: " + Arrays.toString(arr));
        }
        System.out.println("最大堆构建完成: " + Arrays.toString(arr));
        
        // 排序阶段
        System.out.println("\n=== 排序阶段 ===");
        for (int i = n - 1; i > 0; i--) {
            // 交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            System.out.println("交换堆顶与索引 " + i + " 后: " + Arrays.toString(arr));
            
            // 重新堆化
            heapify(arr, i, 0);
            System.out.println("重新堆化后: " + Arrays.toString(arr));
        }
    }
    
    public static void main(String[] args) {
        // 测试用例1：普通数组
        int[] arr1 = {12, 11, 13, 5, 6, 7};
        System.out.println("原始数组:");
        printArray(arr1);
        
        heapSort(arr1);
        System.out.println("排序后数组:");
        printArray(arr1);
        // 输出: 5 6 7 11 12 13
        
        // 测试用例2：带重复元素
        System.out.println("\n--- 测试用例2：带重复元素 ---");
        int[] arr2 = {9, 4, 3, 8, 10, 2, 5, 9, 3};
        System.out.println("原始: " + Arrays.toString(arr2));
        heapSort(arr2);
        System.out.println("排序: " + Arrays.toString(arr2));
        
        // 测试用例3：详细追踪
        System.out.println("\n--- 测试用例3：详细步骤 ---");
        int[] arr3 = {4, 10, 3, 5, 1};
        heapSortWithTrace(arr3);
    }
}

3.4 堆排序复杂度分析

指标 复杂度 说明
时间复杂度（最坏） O(n log n) 每次堆化为O(log n)，执行n次
时间复杂度（最好） O(n log n) 与输入无关，始终一致
时间复杂度（平均） O(n log n) -
空间复杂度 O(1) 原地排序，仅需常数额外空间
稳定性 不稳定 相等元素可能改变相对顺序

3.5 堆排序 Vs 其他排序算法

算法 时间复杂度 空间复杂度 稳定性 适用场景
堆排序 O(n log n) O(1) 不稳定 内存受限，需要保证最坏情况性能
快速排序 O(n log n) O(log n) 不稳定 通用场景，平均性能最好
归并排序 O(n log n) O(n) 稳定 需要稳定排序，链表排序
插入排序 O(n²) O(1) 稳定 小规模数据，基本有序数据

四、总结

二叉堆作为一种基础而强大的数据结构，在计算机科学中有着广泛的应用：

  1. 优先级队列：操作系统任务调度、Dijkstra最短路径算法、Huffman编码等
  2. 堆排序：内存受限环境下的高效排序选择
  3. 图算法：Prim最小生成树、A*寻路算法等
  4. 中位数查找：数据流中的动态中位数维护
  5. Top-K问题：快速查找最大/最小的K个元素

掌握二叉堆的实现原理，是理解更高级数据结构和算法的基础。通过本文提供的Java代码，您可以直接在实际项目中使用或根据需求进行定制优化。

参考资料：

  • GeeksforGeeks - Binary Heap
  • GeeksforGeeks - Heap Sort
  • Interview Cake - Heapsort Algorithm
  • Princeton Algorithms - Priority Queues
算法学习
#算法 #数据结构
二叉堆详解
https://alleyf.github.io/2026/03/a215245c1453.html
作者
alleyf
发布于
2026年3月9日
更新于
2026年3月9日
许可协议