二叉堆详解：原理、实现与应用

1. 什么是二叉堆二叉堆Binary Heap是一种特殊的完全二叉树数据结构它满足堆性质对于最大堆每个节点的值都大于或等于其子节点的值对于最小堆每个节点的值都小于或等于其子节点的值。二叉堆通常用于实现优先队列。2. 二叉堆的特性完全二叉树除了最后一层其他层都是满的且最后一层的节点都靠左排列。堆序性最大堆中父节点值 ≥ 子节点值最小堆中父节点值 ≤ 子节点值。数组表示二叉堆通常用数组存储节省指针空间且父子节点索引关系明确。3. 数组表示与索引关系对于存储在数组中的二叉堆索引从0开始父节点索引parent(i) (i - 1) / 2左子节点索引left(i) 2 * i 1右子节点索引right(i) 2 * i 24. 核心操作4.1 上浮Heapify Up当在堆尾插入新元素时需要将其与父节点比较如果违反堆性质则交换直到满足堆性质为止。4.2 下沉Heapify Down当删除堆顶元素通常将堆尾元素移到堆顶时需要将其与子节点比较如果违反堆性质则与较大的子节点最大堆或较小的子节点最小堆交换直到满足堆性质。4.3 插入元素将新元素添加到数组末尾然后执行上浮操作。4.4 删除堆顶将堆顶元素与最后一个元素交换删除最后一个元素原堆顶然后对新的堆顶执行下沉操作。4.5 建堆从一个无序数组构建堆从最后一个非叶子节点开始向前遍历对每个节点执行下沉操作。5. 代码实现Javapublic class MaxHeap { private int[] heap; private int size; private int capacity; public MaxHeap(int capacity) { this.capacity capacity; this.heap new int[capacity]; this.size 0; } // 获取父节点索引 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; } // 上浮操作 private void heapifyUp(int i) { while (i 0 heap[parent(i)] heap[i]) { swap(i, parent(i)); i parent(i); } } // 下沉操作 private void heapifyDown(int i) { int maxIndex i; int left leftChild(i); int right rightChild(i); if (left size heap[left] heap[maxIndex]) { maxIndex left; } if (right size heap[right] heap[maxIndex]) { maxIndex right; } if (i ! maxIndex) { swap(i, 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 result heap[0]; heap[0] heap[size - 1]; size--; heapifyDown(0); return result; } // 建堆 public void buildHeap(int[] array) { if (array.length capacity) { throw new IllegalArgumentException(Array too large); } System.arraycopy(array, 0, heap, 0, array.length); size array.length; // 从最后一个非叶子节点开始下沉 for (int i size / 2 - 1; i 0; i--) { heapifyDown(i); } } // 获取堆顶元素不删除 public int peek() { if (size 0) { throw new IllegalStateException(Heap is empty); } return heap[0]; } public int size() { return size; } public boolean isEmpty() { return size 0; } }6. 时间复杂度分析插入O(log n) - 上浮操作最多需要 log n 次比较删除堆顶O(log n) - 下沉操作最多需要 log n 次比较建堆O(n) - 看似 O(n log n)但通过数学分析可得 O(n)获取堆顶O(1)7. 应用场景优先队列二叉堆是优先队列的高效实现方式堆排序基于二叉堆的排序算法时间复杂度 O(n log n)Top K 问题使用最小堆维护最大的 K 个元素Dijkstra 算法用于寻找最短路径时维护待处理节点哈夫曼编码构建哈夫曼树时使用优先队列8. 二叉堆 vs 二叉搜索树特性二叉堆二叉搜索树主要用途快速获取最大/最小值快速查找、插入、删除任意元素时间复杂度获取最值 O(1)插入删除 O(log n)查找、插入、删除平均 O(log n)有序性只保证堆性质不完全有序中序遍历有序实现复杂度简单数组存储相对复杂需要指针9. 总结二叉堆是一种简单高效的数据结构特别适合需要频繁获取最大或最小元素的场景。它的数组表示形式节省空间核心操作上浮、下沉的时间复杂度为 O(log n)是优先队列的标准实现方式。掌握二叉堆对于理解更高级的数据结构和算法如堆排序、图算法具有重要意义。