数据结构之堆：解析与应用

一、堆的核心定义与性质

堆是一种特殊的完全二叉树，分为最大堆和最小堆：

• 最大堆：每个节点的值 ≥ 子节点值，根节点为最大值。
• 最小堆：每个节点的值 ≤ 子节点值，根节点为最小值。

关键性质：

1. 完全二叉树：除最后一层外，其他层节点满，且最后一层节点靠左排列。
2. 数组实现：通过索引计算父子节点关系：

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

二、堆的存储结构与操作

1. 存储结构

堆通过数组实现，例如数组 [90, 15, 10, 7, 12, 2, 7, 3] 表示的最小堆：

        90/  \15    10/ \   / \7  12 2   7/
3

2. 基本操作

• 插入（Insert）：

1. 将新元素添加到数组末尾。
2. 通过上浮（Sift Up）调整堆序性：比较新节点与父节点，若违反堆序性则交换，直到满足条件。
3. 时间复杂度：O(log n)。

• 删除堆顶元素（Delete）：

1. 将堆顶元素与末尾元素交换，并删除末尾元素。
2. 通过下沉（Sift Down）调整堆序性：比较当前节点与子节点，若违反堆序性则与较大（最大堆）或较小（最小堆）子节点交换，直到满足条件。
3. 时间复杂度：O(log n)。

• 建堆（Heapify）：
  • 自底向上建堆：从最后一个非叶子节点开始，对每个节点执行下沉操作。
  • 时间复杂度：O(n)（优于逐个插入的 O(n log n)）。
• 堆排序（Heap Sort）：

1. 构建最大堆。
2. 反复将堆顶元素（最大值）与末尾元素交换，并缩小堆的范围，最后对新的堆顶执行下沉操作。

• 时间复杂度：O(n log n)。
• 空间复杂度：O(1)（原地排序）。

三、堆的实现

(一) 基于动态数组实现最大堆

1. 动态数组实现类

import org.omg.CORBA.Object;/*** 动态数组，数组二次封装*/
public class Array<E> {/*** 基于Java原生数组，保存数据的容器*/private E[] data;/*** 当前元素个数*/private int size;public Array(int capacity) {data = (E[]) new Object[capacity];size = 0;}/*** 默认数组容量capacity=10*/public Array() {this(10);}public Array(E[] arr) {data = (E[]) new Object[arr.length];for (int i = 0; i < arr.length; i++) {data[i] = arr[i];}size = arr.length;}/*** 获取数组中元素个数* @return*/public int getSize() {return size;}/*** 获取数组的容量* @return*/public int getCapacity() {return data.length;}/*** 判断数组是否为空* @return*/public boolean isEmpty() {return size == 0;}/*** 在所有元素后面添加新元素* @param e 元素*/public void addLast(E e) {add(size, e);}/*** 在所有元素前面添加新元素* @param e 元素*/public void addFirst(E e) {add(0, e);}/*** 向index索引位置插入一个新元素e* @param index 数组索引位置* @param e 元素*/public void add(int index, E e) {if (index < 0 || index > size) {throw new IllegalArgumentException("addList failed. index < 0 || index > size");}//空间不足，扩容if (size == data.length) {resize(2 * data.length);}for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}data[index] = e;size++;}/*** 根据元素索引获取数组元素* @param index 索引* @return*/public E get(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("get failed. index is illegal");}return data[index];}/*** 根据元素索引修改数组元素* @param index 索引* @param e 元素* @return*/public void set(int index, E e) {if (index < 0 || index >= size) {throw new IllegalArgumentException("get failed. index is illegal");}data[index] = e;}/*** 判断包含元素* @param e 元素* @return*/public boolean contains(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e)) {return true;}}return false;}/*** 查找元素索引* @param e 元素* @return 返回元素索引，如果不存在则返回-1*/public int find(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e)) {return i;}}return -1;}/*** 移除指定索引的元素* @param index 索引* @return 返回被移除的元素*/public E remove(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("get failed. index is illegal");}E ret = data[index];for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--;data[size] = null;//空间利用率低，数组缩容，防止复杂度震荡if (size == data.length / 4 && data.length / 2 != 0) {resize(data.length / 2);}return ret;}/*** 移除第一个元素* @return 返回被移除元素*/public E removeFirst() {return remove(0);}/*** 移除最后一个元素* @return 返回被移除元素*/public E removeLast() {return remove(size - 1);}/*** 移除数组中一个元素* @param e 元素*/public void removeElement(E e) {int index = find(e);if (index != -1) {remove(index);}}/*** 数组容器扩容、缩容* @param newCapacity 新的容量*/private void resize(int newCapacity) {E[] newData = (E[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newData[i] = data[i];}data = newData;}/*** 交换数组中两个索引对应的元素* @param i 元素* @param j 元素*/public void swap(int i, int j) {if (i < 0 || i >= size || j < 0 || j >= size) {throw new IllegalArgumentException("index is illegal");}E e = data[i];data[i] = data[j];data[j] = e;}@Overridepublic String toString() {StringBuilder res = new StringBuilder();res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));res.append("[");for (int i = 0; i < size; i++) {res.append(data[i]);if (i != size - 1) {res.append(", ");}}res.append("]");return res.toString();}}

2. 基于动态数组实现最大堆

/*** 基于动态数组实现最大堆* @param <E>*/
public class MaxHeap<E extends Comparable<E>> {private Array<E> data;public MaxHeap(int capacity) {data = new Array<>(capacity);}public MaxHeap() {data = new Array<>();}/*** 普通数组堆化* @param arr*/public MaxHeap(E[] arr) {data = new Array<>(arr);//从第一个非叶子节点（叶子节点无需下沉操作）开始遍历，并且执行下沉操作，完成堆化for (int i = parent(arr.length - 1); i >= 0; i--) {siftDown(i);}}/*** 获取堆中元素个数* @return*/public int size() {return data.getSize();}/*** 判断堆中是否为空* @return*/public boolean isEmpty() {return data.isEmpty();}/*** 返回二叉堆的数组表示中，一个索引所表示的元素的父亲节点的索引* @param index 节点在数组中的索引* @return*/private int parent(int index) {if (index == 0) {throw new IllegalArgumentException("index-0 doesn't have parent");}return (index - 1) / 2;}/*** 返回二叉堆的数组表示中，一个索引所表示的元素的左孩子节点的索引* @param index 节点在数组中的索引* @return*/private int leftChild(int index) {return index * 2 + 1;}/*** 返回二叉堆的数组表示中，一个索引所表示的元素的右孩子节点的索引* @param index 节点在数组中的索引* @return*/private int rightChild(int index) {return index * 2 + 2;}/*** 向堆中添加元素* @param e 待添加元素*/public void add(E e) {data.addLast(e);siftUp(data.getSize() - 1);}/*** 堆中元素上浮* @param k 元素索引*/private void siftUp(int k) {//当前节点的元素比父亲节点的元素大则上浮while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {//交换数组中的元素data.swap(k, parent(k));k = parent(k);}}/*** 查询堆中最大元素* @return*/public E findMax() {if (data.getSize() == 0) {throw new IllegalArgumentException("can not finMax when heap is empty");}return data.get(0);}/*** 取出堆中最大元素* @return*/public E extractMax() {E max = findMax();//交换堆中最大的元素与堆尾元素data.swap(0, data.getSize() - 1);//删除堆尾元素data.removeLast();//元素下沉siftDown(0);return max;}/*** 堆中元素下沉* @param k 元素索引*/private void siftDown(int k) {//只要该元素的左孩子索引没有越界，继续处理while (leftChild(k) < data.getSize()) {int j = leftChild(k);if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {j = rightChild(k);}//data[j] 是leftChild 和 rightChild中的最大值if (data.get(k).compareTo(data.get(j)) >= 0) {break;}//下沉data.swap(k, j);k = j;}}/*** 取出堆中的最大元素，并且替换成元素e* @param e 待替换元素* @return 堆中最大元素*/public E replace(E e) {E max = findMax();//覆盖最大元素data.set(0, e);//被元素可能破坏了堆的结构，触发下沉操作siftDown(0);return max;}}

四、堆的应用场景

(一) 优先队列：

• 堆是优先队列的天然实现，支持高效插入和删除最高优先级元素。
  • 例如：任务调度、Dijkstra算法中的最短路径选择。

(二) Top-K问题：

• 维护一个大小为K的最小堆（求前K大）或最大堆（求前K小），快速找到极值。
  • 例如：统计日志中的Top 100高频词。

(三) 中位数与百分位数：

• 使用两个堆（最大堆和最小堆）动态维护数据流的中位数或特定百分位值。

(四) 合并有序文件：

• 将多个有序小文件的头部元素插入最小堆，依次提取最小值合并到结果文件。

五、堆与其他数据结构的对比

特性	堆	二叉搜索树（BST）	平衡二叉搜索树（如AVL树）
有序性	仅保证堆序性（父子关系）	中序遍历有序	完全有序
插入/删除	O(log n)	平均 O(log n)，最坏 O(n)	O(log n)
查找	不支持高效查找	O(log n)（平衡时）	O(log n)
适用场景	优先队列、堆排序	需要频繁查找的场景	需要高效查找、插入、删除的场景

六、堆的变种与扩展

1. 斐波那契堆：支持更高效的合并操作（均摊 O(1)），常用于动态图算法（如Prim算法）。
2. 左偏树：具有高效的合并性能，适用于需要频繁合并堆的场景。

七、总结

堆是一种高效的树形数据结构，通过完全二叉树和数组的结合，实现了插入、删除和建堆等操作的高效性。其核心思想是通过“上浮”和“下沉”操作维护堆序性，适用于需要快速访问最大值或最小值的场景。理解堆的实现和操作是掌握高级算法（如堆排序、Dijkstra算法）的基础，也是解决大规模数据问题的关键工具。