二叉堆

算法

二叉堆是一种特殊的完全二叉树,常用于实现优先队列。最小堆的每个节点的值都小于或等于其子节点的值,最大堆的每个节点的值都大于或等于其子节点的值。二叉堆支持高效的插入、删除最值和构建操作。

空间复杂度:O(n)

算法讲解

二叉堆

介绍

二叉堆是一种特殊的完全二叉树数据结构,它满足堆属性。完全二叉树是指除了最后一层外,其他层的节点都是满的,而最后一层的节点都靠左排列。二叉堆主要有两种类型:

  • 最大堆:每个父节点的值都大于或等于其子节点的值
  • 最小堆:每个父节点的值都小于或等于其子节点的值

二叉堆的这种特殊结构使得它可以高效地找到最大值或最小值,所以也常被用来实现优先队列。

核心特性

  1. 完全二叉树结构:除最底层外,每层都填满,且最底层从左到右填充
  2. 堆序性质:
    • 最大堆:父节点值 ≥ 子节点值
    • 最小堆:父节点值 ≤ 子节点值
  3. 高效的顶部元素访问:可以在O(1)时间内获取最大/最小元素
  4. 数组表示:虽然概念上是树结构,但通常用数组实现,这样可以节省指针开销并提高内存局部性

基本操作

插入元素(Insert)

向堆中添加一个新元素:

  • 首先将新元素添加到堆的末尾
  • 然后通过"上浮"操作调整堆,直到满足堆性质

删除顶部元素(Extract-Max/Min)

移除并返回堆顶元素(最大/最小值):

  • 取出堆顶元素
  • 将堆的最后一个元素移到堆顶
  • 通过"下沉"操作调整堆,直到满足堆性质

上浮(Heapify-Up)

将一个元素向上移动到合适位置的过程:

  • 比较当前元素与其父节点
  • 如果不满足堆性质,则交换它们
  • 重复此过程直到满足堆性质

下沉(Heapify-Down)

将一个元素向下移动到合适位置的过程:

  • 比较当前元素与其最大(或最小)的子节点
  • 如果不满足堆性质,则交换它们
  • 重复此过程直到满足堆性质

基础实现

代码实现

Java 实现

▼
Java
复制代码
public class MinHeap { private int[] heap; private int size; private int capacity; // 构造函数 public MinHeap(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; } // 插入元素 public void insert(int key) { if (size == capacity) { System.out.println("堆已满,无法插入"); return; } // 先将新元素插入到堆的末尾 heap[size] = key; int current = size; size++; // 上浮操作:将元素向上移动到合适位置 while (current > 0 && heap[current] < heap[parent(current)]) { swap(current, parent(current)); current = parent(current); } } // 获取最小元素(不删除) public int peek() { if (size <= 0) { System.out.println("堆为空"); return -1; } return heap[0]; } // 删除并返回最小元素 public int extractMin() { if (size <= 0) { System.out.println("堆为空"); return -1; } if (size == 1) { size--; return heap[0]; } // 存储根节点(最小值) int root = heap[0]; // 将最后一个元素放到根位置 heap[0] = heap[size - 1]; size--; // 下沉操作:将根元素向下移动到合适位置 heapifyDown(0); return root; } // 下沉操作 private void heapifyDown(int i) { int smallest = i; int left = leftChild(i); int right = rightChild(i); // 找出当前节点、左子节点和右子节点中的最小值 if (left < size && heap[left] < heap[smallest]) { smallest = left; } if (right < size && heap[right] < heap[smallest]) { smallest = right; } // 如果最小值不是当前节点,则交换并继续下沉 if (smallest != i) { swap(i, smallest); heapifyDown(smallest); } } // 打印堆 public void printHeap() { for (int i = 0; i < size; i++) { System.out.print(heap[i] + " "); } System.out.println(); } public static void main(String[] args) { MinHeap minHeap = new MinHeap(10); minHeap.insert(5); minHeap.insert(3); minHeap.insert(8); minHeap.insert(1); minHeap.insert(10); System.out.println("构建的堆:"); minHeap.printHeap(); System.out.println("最小元素:" + minHeap.peek()); System.out.println("提取最小元素:" + minHeap.extractMin()); System.out.println("提取后的堆:"); minHeap.printHeap(); } }

JavaScript 实现

▼
Javascript
复制代码
class MinHeap { constructor(capacity) { this.capacity = capacity; this.size = 0; this.heap = new Array(capacity); } // 获取父节点索引 parent(i) { return Math.floor((i - 1) / 2); } // 获取左子节点索引 leftChild(i) { return 2 * i + 1; } // 获取右子节点索引 rightChild(i) { return 2 * i + 2; } // 交换两个节点 swap(i, j) { const temp = this.heap[i]; this.heap[i] = this.heap[j]; this.heap[j] = temp; } // 插入元素 insert(key) { if (this.size === this.capacity) { console.log("堆已满,无法插入"); return; } // 先将新元素插入到堆的末尾 this.heap[this.size] = key; let current = this.size; this.size++; // 上浮操作:将元素向上移动到合适位置 while (current > 0 && this.heap[current] < this.heap[this.parent(current)]) { this.swap(current, this.parent(current)); current = this.parent(current); } } // 获取最小元素(不删除) peek() { if (this.size <= 0) { console.log("堆为空"); return -1; } return this.heap[0]; } // 删除并返回最小元素 extractMin() { if (this.size <= 0) { console.log("堆为空"); return -1; } if (this.size === 1) { this.size--; return this.heap[0]; } // 存储根节点(最小值) const root = this.heap[0]; // 将最后一个元素放到根位置 this.heap[0] = this.heap[this.size - 1]; this.size--; // 下沉操作:将根元素向下移动到合适位置 this.heapifyDown(0); return root; } // 下沉操作 heapifyDown(i) { let smallest = i; const left = this.leftChild(i); const right = this.rightChild(i); // 找出当前节点、左子节点和右子节点中的最小值 if (left < this.size && this.heap[left] < this.heap[smallest]) { smallest = left; } if (right < this.size && this.heap[right] < this.heap[smallest]) { smallest = right; } // 如果最小值不是当前节点,则交换并继续下沉 if (smallest !== i) { this.swap(i, smallest); this.heapifyDown(smallest); } } // 打印堆 printHeap() { let output = ""; for (let i = 0; i < this.size; i++) { output += this.heap[i] + " "; } console.log(output); } } // 使用示例 function main() { const minHeap = new MinHeap(10); minHeap.insert(5); minHeap.insert(3); minHeap.insert(8); minHeap.insert(1); minHeap.insert(10); console.log("构建的堆:"); minHeap.printHeap(); console.log("最小元素:" + minHeap.peek()); console.log("提取最小元素:" + minHeap.extractMin()); console.log("提取后的堆:"); minHeap.printHeap(); } main();

Python 实现

▼
Python
复制代码
class MinHeap: def __init__(self, capacity): self.capacity = capacity self.size = 0 self.heap = [0] * capacity # 获取父节点索引 def parent(self, i): return (i - 1) // 2 # 获取左子节点索引 def left_child(self, i): return 2 * i + 1 # 获取右子节点索引 def right_child(self, i): return 2 * i + 2 # 交换两个节点 def swap(self, i, j): self.heap[i], self.heap[j] = self.heap[j], self.heap[i] # 插入元素 def insert(self, key): if self.size == self.capacity: print("堆已满,无法插入") return # 先将新元素插入到堆的末尾 self.heap[self.size] = key current = self.size self.size += 1 # 上浮操作:将元素向上移动到合适位置 while current > 0 and self.heap[current] < self.heap[self.parent(current)]: self.swap(current, self.parent(current)) current = self.parent(current) # 获取最小元素(不删除) def peek(self): if self.size <= 0: print("堆为空") return -1 return self.heap[0] # 删除并返回最小元素 def extract_min(self): if self.size <= 0: print("堆为空") return -1 if self.size == 1: self.size -= 1 return self.heap[0] # 存储根节点(最小值) root = self.heap[0] # 将最后一个元素放到根位置 self.heap[0] = self.heap[self.size - 1] self.size -= 1 # 下沉操作:将根元素向下移动到合适位置 self.heapify_down(0) return root # 下沉操作 def heapify_down(self, i): smallest = i left = self.left_child(i) right = self.right_child(i) # 找出当前节点、左子节点和右子节点中的最小值 if left < self.size and self.heap[left] < self.heap[smallest]: smallest = left if right < self.size and self.heap[right] < self.heap[smallest]: smallest = right # 如果最小值不是当前节点,则交换并继续下沉 if smallest != i: self.swap(i, smallest) self.heapify_down(smallest) # 打印堆 def print_heap(self): print(" ".join(str(self.heap[i]) for i in range(self.size))) # 使用示例 def main(): min_heap = MinHeap(10) min_heap.insert(5) min_heap.insert(3) min_heap.insert(8) min_heap.insert(1) min_heap.insert(10) print("构建的堆:") min_heap.print_heap() print("最小元素:", min_heap.peek()) print("提取最小元素:", min_heap.extract_min()) print("提取后的堆:") min_heap.print_heap() if __name__ == "__main__": main()

Go 实现

▼
Go
复制代码
package main import "fmt" // MinHeap 表示最小堆结构 type MinHeap struct { heap []int // 堆数组 size int // 当前堆大小 capacity int // 堆最大容量 } // NewMinHeap 创建一个指定容量的最小堆 func NewMinHeap(capacity int) *MinHeap { return &MinHeap{ heap: make([]int, capacity), size: 0, capacity: capacity, } } // 获取父节点索引 func (mh *MinHeap) parent(i int) int { return (i - 1) / 2 } // 获取左子节点索引 func (mh *MinHeap) leftChild(i int) int { return 2*i + 1 } // 获取右子节点索引 func (mh *MinHeap) rightChild(i int) int { return 2*i + 2 } // 交换两个节点的值 func (mh *MinHeap) swap(i, j int) { mh.heap[i], mh.heap[j] = mh.heap[j], mh.heap[i] } // Insert 向堆中插入新元素 func (mh *MinHeap) Insert(key int) { if mh.size == mh.capacity { fmt.Println("堆已满,无法插入") return } // 先将新元素插入到堆的末尾 mh.heap[mh.size] = key current := mh.size mh.size++ // 上浮操作:将元素向上移动到合适位置 for current > 0 && mh.heap[current] < mh.heap[mh.parent(current)] { mh.swap(current, mh.parent(current)) current = mh.parent(current) } } // Peek 获取堆顶元素(不删除) func (mh *MinHeap) Peek() int { if mh.size <= 0 { fmt.Println("堆为空") return -1 } return mh.heap[0] } // ExtractMin 删除并返回堆顶元素 func (mh *MinHeap) ExtractMin() int { if mh.size <= 0 { fmt.Println("堆为空") return -1 } if mh.size == 1 { mh.size-- return mh.heap[0] } // 存储根节点(最小值) root := mh.heap[0] // 将最后一个元素放到根位置 mh.heap[0] = mh.heap[mh.size-1] mh.size-- // 下沉操作:将根元素向下移动到合适位置 mh.heapifyDown(0) return root } // 下沉操作 func (mh *MinHeap) heapifyDown(i int) { smallest := i left := mh.leftChild(i) right := mh.rightChild(i) // 找出当前节点、左子节点和右子节点中的最小值 if left < mh.size && mh.heap[left] < mh.heap[smallest] { smallest = left } if right < mh.size && mh.heap[right] < mh.heap[smallest] { smallest = right } // 如果最小值不是当前节点,则交换并继续下沉 if smallest != i { mh.swap(i, smallest) mh.heapifyDown(smallest) } } // PrintHeap 打印堆的内容 func (mh *MinHeap) PrintHeap() { for i := 0; i < mh.size; i++ { fmt.Printf("%d ", mh.heap[i]) } fmt.Println() } func main() { minHeap := NewMinHeap(10) minHeap.Insert(5) minHeap.Insert(3) minHeap.Insert(8) minHeap.Insert(1) minHeap.Insert(10) fmt.Println("构建的堆:") minHeap.PrintHeap() fmt.Printf("最小元素:%d\n", minHeap.Peek()) fmt.Printf("提取最小元素:%d\n", minHeap.ExtractMin()) fmt.Println("提取后的堆:") minHeap.PrintHeap() }

C++ 实现

▼
C++
复制代码
#include <iostream> #include <vector> class MinHeap { private: std::vector<int> heap; int size; int capacity; // 获取父节点索引 int parent(int i) { return (i - 1) / 2; } // 获取左子节点索引 int leftChild(int i) { return 2 * i + 1; } // 获取右子节点索引 int rightChild(int i) { return 2 * i + 2; } // 交换两个节点 void swap(int i, int j) { int temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } // 下沉操作 void heapifyDown(int i) { int smallest = i; int left = leftChild(i); int right = rightChild(i); // 找出当前节点、左子节点和右子节点中的最小值 if (left < size && heap[left] < heap[smallest]) { smallest = left; } if (right < size && heap[right] < heap[smallest]) { smallest = right; } // 如果最小值不是当前节点,则交换并继续下沉 if (smallest != i) { swap(i, smallest); heapifyDown(smallest); } } public: // 构造函数 MinHeap(int cap) { capacity = cap; size = 0; heap.resize(capacity); } // 插入元素 void insert(int key) { if (size == capacity) { std::cout << "堆已满,无法插入" << std::endl; return; } // 先将新元素插入到堆的末尾 heap[size] = key int current = size size++ // 上浮操作:将元素向上移动到合适位置 while (current > 0 && heap[current] < heap[parent(current)]) { swap(current, parent(current)) current = parent(current) } } // 获取最小元素(不删除) int peek() { if (size <= 0) { std::cout << "堆为空" << std::endl; return -1; } return heap[0]; } // 删除并返回最小元素 int extractMin() { if (size <= 0) { std::cout << "堆为空" << std::endl; return -1; } if (size == 1) { size-- return heap[0] } // 存储根节点(最小值) int root = heap[0] // 将最后一个元素放到根位置 heap[0] = heap[size - 1] size-- // 下沉操作:将根元素向下移动到合适位置 heapifyDown(0) return root } // 打印堆 void printHeap() { for (int i = 0; i < size; i++) { std::cout << heap[i] << " "; } std::cout << std::endl; } }; int main() { MinHeap minHeap(10); minHeap.insert(5); minHeap.insert(3); minHeap.insert(8); minHeap.insert(1); minHeap.insert(10); std::cout << "构建的堆:" << std::endl; minHeap.printHeap(); std::cout << "最小元素:" << minHeap.peek() << std::endl; std::cout << "提取最小元素:" << minHeap.extractMin() << std::endl; std::cout << "提取后的堆:" << std::endl; minHeap.printHeap(); return 0; }

这两个实现都保持了二叉堆的基本操作和性能特性,但分别采用了Go和C++语言的特定语法和风格。

Go实现使用了Go语言的特性,如方法接收器和多返回值交换,而C++实现则利用了面向对象特性和STL容器(vector)来存储堆元素。两者都实现了相同的功能:创建堆、插入元素、获取最小元素、提取最小元素等操作。

优缺点

优点

  1. 高效的优先级操作:O(1) 时间复杂度查找最大/最小元素
  2. 相对较快的插入和删除:O(log n) 时间复杂度
  3. 空间效率高:数组实现不需要额外的指针开销
  4. 实现简单:相比其他高级数据结构,二叉堆实现相对简单
  5. 内存局部性好:连续内存存储提高缓存命中率

缺点

  1. 有限的操作集:只支持查找最值,不支持高效的搜索、删除任意元素等操作
  2. 不支持快速合并:合并两个堆的操作较为复杂
  3. 不稳定性:相同优先级的元素,其相对顺序可能改变
  4. 对缓存不友好的访问模式:特别是在堆较大时,父子节点间的跳跃访问可能导致缓存未命中

应用场景

二叉堆广泛应用于各种算法和系统中:

  1. 优先队列实现:当需要频繁获取最大或最小元素时,二叉堆是最常用的数据结构。操作系统中的进程调度、网络路由算法都会使用优先队列来确定下一个处理的任务。
  2. 排序算法:堆排序利用二叉堆的特性,能够以O(n log n)的时间复杂度对数据进行排序,且空间复杂度为O(1),适合大数据排序。
  3. 图算法:许多图算法如Dijkstra最短路径、Prim最小生成树算法都使用优先队列来选择下一个处理的节点,二叉堆是其高效实现。
  4. 中位数和百分位数计算:通过维护两个堆(最大堆和最小堆),可以高效地跟踪数据流的中位数和其他统计值。
  5. 事件模拟:在离散事件模拟中,事件按时间顺序处理,优先队列可以确保按正确顺序处理事件。
  6. 数据流处理:在处理大量数据流时,如果只需要关注"最重要"的k个元素,可以维护一个大小为k的堆。

扩展

Java标准库中的堆实现

Java 提供了 PriorityQueue 类,它基于二叉堆实现:

▼
Java
复制代码
import java.util.PriorityQueue; public class PriorityQueueExample { public static void main(String[] args) { // 默认是最小堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 添加元素 minHeap.add(5); minHeap.add(3); minHeap.add(8); minHeap.add(1); minHeap.add(10); System.out.println("优先队列内容:" + minHeap); System.out.println("最小元素:" + minHeap.peek()); System.out.println("提取最小元素:" + minHeap.poll()); System.out.println("提取后的优先队列:" + minHeap); // 创建最大堆(通过自定义比较器) PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); maxHeap.add(5); maxHeap.add(3); maxHeap.add(8); maxHeap.add(1); maxHeap.add(10); System.out.println("最大堆内容:" + maxHeap); System.out.println("最大元素:" + maxHeap.peek()); } }

堆的变种

除了基本的二叉堆,还有几种重要的堆变种:

  1. d叉堆(d-ary Heap):每个节点最多有d个子节点,而不是2个。增加d值可以减少堆的高度,在某些应用中可以提高性能。
  2. 斐波那契堆(Fibonacci Heap):一种更复杂的堆结构,提供了更高效的合并操作和摊销时间复杂度。许多高级图算法使用斐波那契堆来提高性能。
  3. 左偏树(Leftist Heap):一种支持高效合并操作的堆,常用于并行计算和分布式系统。
  4. 配对堆(Pairing Heap):结构简单但性能优异的堆实现,特别适合需要频繁合并和减小键值的应用。

测验

  1. 二叉堆是一种什么样的数据结构?它有哪两种主要类型?
  2. 如果一个最小堆的数组表示为 [3, 5, 8, 6, 9, 10, 12],那么元素5的左右子节点分别是什么?
  3. 在一个包含n个元素的二叉堆中,查找最大/最小元素、插入新元素和删除堆顶元素的时间复杂度分别是多少?
  4. 如果要将一个无序数组转换为堆,最坏情况下的时间复杂度是多少?
  5. 为什么二叉堆通常使用数组而不是链表来实现?

测验答案

  1. 二叉堆是一种特殊的完全二叉树数据结构,它满足堆属性。主要有两种类型:最大堆(父节点值大于等于子节点值)和最小堆(父节点值小于等于子节点值)。
  2. 在数组表示的堆中,如果一个节点的索引是i,那么它的左子节点索引是2i+1,右子节点索引是2i+2。元素5的索引是1,所以它的左子节点是索引为3的元素6,右子节点是索引为4的元素9。
  3. 1)查找最大/最小元素:O(1) 2)插入新元素:O(log n) 3)删除堆顶元素:O(log n)
  4. 将无序数组转换为堆的时间复杂度是O(n),这比直观预期的O(n log n)要好。因为使用了自底向上的建堆方法,对大多数节点只需要很少的下沉操作。
  5. 二叉堆使用数组实现有几个优点:1) 不需要额外的指针开销,节省内存;2) 利用索引公式可以直接计算父子节点位置,无需存储额外引用;3) 数组的连续内存分配提供了更好的内存局部性,有利于缓存性能;4) 实现简单,易于理解和维护。

相关的 LeetCode 热门题目

  1. 23. 合并K个排序链表 - 使用最小堆来高效合并多个有序链表。
  2. 347. 前 K 个高频元素 - 使用堆来找出数组中出现频率最高的K个元素。
  3. 295. 数据流的中位数 - 使用一个最大堆和一个最小堆来跟踪数据流的中位数。