Heap (Priority Queue) Data Structure in Hello-Algo: From Definitions to Array-Based Implementation【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇技术指南以《Hello 算法》英文版堆章节 heap.md 为骨架系统讲解堆大顶堆/小顶堆的数学定义、完全二叉树性质以及如何用各语言内置的优先队列类完成push/pop/peek等常见操作。同时结合仓库中 my_heap.py 等源码深入拆解基于数组的堆存储表示、sift up与sift down两个核心堆化过程并说明堆在优先队列、堆排序与 Top-K 问题中的典型应用场景。堆heap是一种满足特定条件的完全二叉树主要可分为两种类型小顶堆min heap任意节点的值 $\leq$ 其子节点的值。大顶堆max heap任意节点的值 $\geq$ 其子节点的值。作为完全二叉树的一个特殊情形堆具有以下特征最底层节点从左到右填充其余层的节点都被完全填满将二叉树的根节点称为“堆顶”将底层最右端的节点称为“堆底”对于大顶堆小顶堆堆顶元素根节点的值是最大最小的。堆的常见操作许多编程语言提供了优先队列priority queue这一抽象数据结构其本质是一个按优先级顺序出队的队列。事实上堆通常被用来实现优先队列大顶堆对应元素按降序出队的优先队列。从使用角度看可以认为“优先队列”与“堆”是等价的数据结构因此本教程对两者不作特殊区分统一以“堆”相称。堆的常见操作及其时间复杂度如下表所示方法名需依据具体语言确定方法名说明时间复杂度push()元素入堆$O(\log n)$pop()堆顶元素出堆$O(\log n)$peek()访问堆顶元素大/小顶堆中的最大值/最小值$O(1)$size()获取堆中元素个数$O(1)$isEmpty()判断堆是否为空$O(1)$在实际应用中可以直接使用编程语言提供的堆类或优先队列类。与排序算法中的“升序”“降序”类似可以通过设置一个flag或修改Comparator比较器来实现“小顶堆”与“大顶堆”之间的转换。例如仓库中的 heap.py 便是通过flag -1将元素取负后入堆从而借助 Python 默认的小顶堆heapq模拟出大顶堆。Python基于 heapq 的正负号取巧# Initialize a min heap min_heap, flag [], 1 # Initialize a max heap max_heap, flag [], -1 # Pythons heapq module implements a min heap by default # Consider negating elements before pushing them to the heap, which inverts the size relationship and thus implements a max heap # In this example, flag 1 corresponds to a min heap, flag -1 corresponds to a max heap # Push elements into the heap heapq.heappush(max_heap, flag * 1) heapq.heappush(max_heap, flag * 3) heapq.heappush(max_heap, flag * 2) heapq.heappush(max_heap, flag * 5) heapq.heappush(max_heap, flag * 4) # Get the heap top element peek: int flag * max_heap[0] # 5 # Remove the heap top element # The removed elements will form a descending sequence val flag * heapq.heappop(max_heap) # 5 val flag * heapq.heappop(max_heap) # 4 val flag * heapq.heappop(max_heap) # 3 val flag * heapq.heappop(max_heap) # 2 val flag * heapq.heappop(max_heap) # 1 # Get the heap size size: int len(max_heap) # Check if the heap is empty is_empty: bool not max_heap # Build a heap from an input list min_heap: list[int] [1, 3, 2, 5, 4] heapq.heapify(min_heap)对应完整可运行示例见 en/codes/python/chapter_heap/heap.py它使用print_heap以树形方式直观打印每次入堆、出堆后的堆结构。C通过比较器区分大小顶堆/* Initialize a heap */ // Initialize a min heap priority_queueint, vectorint, greaterint minHeap; // Initialize a max heap priority_queueint, vectorint, lessint maxHeap; /* Push elements into the heap */ maxHeap.push(1); maxHeap.push(3); maxHeap.push(2); maxHeap.push(5); maxHeap.push(4); /* Get the heap top element */ int peek maxHeap.top(); // 5 /* Remove the heap top element */ // The removed elements will form a descending sequence maxHeap.pop(); // 5 maxHeap.pop(); // 4 maxHeap.pop(); // 3 maxHeap.pop(); // 2 maxHeap.pop(); // 1 /* Get the heap size */ int size maxHeap.size(); /* Check if the heap is empty */ bool isEmpty maxHeap.empty(); /* Build a heap from an input list */ vectorint input{1, 3, 2, 5, 4}; priority_queueint, vectorint, greaterint minHeap(input.begin(), input.end());Java用 Lambda 改写 Comparator/* Initialize a heap */ // Initialize a min heap QueueInteger minHeap new PriorityQueue(); // Initialize a max heap (use lambda expression to modify Comparator) QueueInteger maxHeap new PriorityQueue((a, b) - b - a); /* Push elements into the heap */ maxHeap.offer(1); maxHeap.offer(3); maxHeap.offer(2); maxHeap.offer(5); maxHeap.offer(4); /* Get the heap top element */ int peek maxHeap.peek(); // 5 /* Remove the heap top element */ // The removed elements will form a descending sequence peek maxHeap.poll(); // 5 peek maxHeap.poll(); // 4 peek maxHeap.poll(); // 3 peek maxHeap.poll(); // 2 peek maxHeap.poll(); // 1 /* Get the heap size */ int size maxHeap.size(); /* Check if the heap is empty */ boolean isEmpty maxHeap.isEmpty(); /* Build a heap from an input list */ minHeap new PriorityQueue(Arrays.asList(1, 3, 2, 5, 4));C#使用 Comparer 控制优先级/* Initialize a heap */ // Initialize a min heap PriorityQueueint, int minHeap new(); // Initialize a max heap (use lambda expression to modify Comparer) PriorityQueueint, int maxHeap new(Comparerint.Create((x, y) y.CompareTo(x))); /* Push elements into the heap */ maxHeap.Enqueue(1, 1); maxHeap.Enqueue(3, 3); maxHeap.Enqueue(2, 2); maxHeap.Enqueue(5, 5); maxHeap.Enqueue(4, 4); /* Get the heap top element */ int peek maxHeap.Peek();//5 /* Remove the heap top element */ // The removed elements will form a descending sequence peek maxHeap.Dequeue(); // 5 peek maxHeap.Dequeue(); // 4 peek maxHeap.Dequeue(); // 3 peek maxHeap.Dequeue(); // 2 peek maxHeap.Dequeue(); // 1 /* Get the heap size */ int size maxHeap.Count; /* Check if the heap is empty */ bool isEmpty maxHeap.Count 0; /* Build a heap from an input list */ minHeap new PriorityQueueint, int([(1, 1), (3, 3), (2, 2), (5, 5), (4, 4)]);C# 的PriorityQueueTElement, TPriority元素与优先级分离Enqueue的第二个参数即优先级同一元素值1..5时以其自身作为优先级。Go实现 heap.Interface 与 sort.InterfaceGo 标准库container/heap只提供堆化的调度逻辑需要自定义类型同时实现heap.Interface与内嵌的sort.Interface。仓库中的 en/codes/go/chapter_heap/heap.go 给出了可直接运行的实现含TestHeap单元测试// In Go, we can construct a max heap of integers by implementing heap.Interface // Implementing heap.Interface also requires implementing sort.Interface type intHeap []any // Push implements the heap.Interface method for pushing an element into the heap func (h *intHeap) Push(x any) { // Push and Pop use pointer receiver as parameters // because they not only adjust the slice contents but also modify the slice length *h append(*h, x.(int)) } // Pop implements the heap.Interface method for popping the heap top element func (h *intHeap) Pop() any { // The element to be removed is stored at the end last : (*h)[len(*h)-1] *h (*h)[:len(*h)-1] return last } // Len is a sort.Interface method func (h *intHeap) Len() int { return len(*h) } // Less is a sort.Interface method func (h *intHeap) Less(i, j int) bool { // To implement a min heap, change this to a less-than sign return (*h)[i].(int) (*h)[j].(int) } // Swap is a sort.Interface method func (h *intHeap) Swap(i, j int) { (*h)[i], (*h)[j] (*h)[j], (*h)[i] } // Top gets the heap top element func (h *intHeap) Top() any { return (*h)[0] } /* Driver Code */ func TestHeap(t *testing.T) { /* Initialize a heap */ // Initialize a max heap maxHeap : intHeap{} heap.Init(maxHeap) /* Push elements into the heap */ // Call heap.Interface methods to add elements heap.Push(maxHeap, 1) heap.Push(maxHeap, 3) heap.Push(maxHeap, 2) heap.Push(maxHeap, 4) heap.Push(maxHeap, 5) /* Get the heap top element */ top : maxHeap.Top() fmt.Printf(Heap top element is %d\n, top) /* Remove the heap top element */ // Call heap.Interface methods to remove elements heap.Pop(maxHeap) // 5 heap.Pop(maxHeap) // 4 heap.Pop(maxHeap) // 3 heap.Pop(maxHeap) // 2 heap.Pop(maxHeap) // 1 /* Get the heap size */ size : len(*maxHeap) fmt.Printf(Number of heap elements is %d\n, size) /* Check if the heap is empty */ isEmpty : len(*maxHeap) 0 fmt.Printf(Is the heap empty? %t\n, isEmpty) }需要注意的是Go 中heap.Pop与heap.Push的“物理删除/追加”发生在自定义的Pop/Push方法内因而必须使用指针接收者。将Less中的改为即可转为小顶堆。Rust借助 std::cmp::Reverse 翻转use std::collections::BinaryHeap; use std::cmp::Reverse; /* Initialize a heap */ // Initialize a min heap let mut min_heap BinaryHeap::Reversei32::new(); // Initialize a max heap let mut max_heap BinaryHeap::new(); /* Push elements into the heap */ max_heap.push(1); max_heap.push(3); max_heap.push(2); max_heap.push(5); max_heap.push(4); /* Get the heap top element */ let peek max_heap.peek().unwrap(); // 5 /* Remove the heap top element */ // The removed elements will form a descending sequence let peek max_heap.pop().unwrap(); // 5 let peek max_heap.pop().unwrap(); // 4 let peek max_heap.pop().unwrap(); // 3 let peek max_heap.pop().unwrap(); // 2 let peek max_heap.pop().unwrap(); // 1 /* Get the heap size */ let size max_heap.len(); /* Check if the heap is empty */ let is_empty max_heap.is_empty(); /* Build a heap from an input list */ let min_heap BinaryHeap::from(vec![Reverse(1), Reverse(3), Reverse(2), Reverse(5), Reverse(4)]);Rust 的BinaryHeap默认是大顶堆用ReverseT包装元素即可实现小顶堆同时也可用BinaryHeap::from从向量线性建堆。Swiftswift-collections 中的 Heap 类型/* Initialize a heap */ // Swifts Heap type supports both max heaps and min heaps, and requires importing swift-collections var heap HeapInt() /* Push elements into the heap */ heap.insert(1) heap.insert(3) heap.insert(2) heap.insert(5) heap.insert(4) /* Get the heap top element */ var peek heap.max()! /* Remove the heap top element */ peek heap.removeMax() // 5 peek heap.removeMax() // 4 peek heap.removeMax() // 3 peek heap.removeMax() // 2 peek heap.removeMax() // 1 /* Get the heap size */ let size heap.count /* Check if the heap is empty */ let isEmpty heap.isEmpty /* Build a heap from an input list */ let heap2 Heap([1, 3, 2, 5, 4])注意swift-collections中的Heap同时支持 max/min 两种语义默认heap.max()取出最大值改用heap.min()/heap.removeMin()即为小顶堆行为。KotlinLambda 改写比较器/* Initialize a heap */ // Initialize a min heap var minHeap PriorityQueueInt() // Initialize a max heap (use lambda expression to modify Comparator) val maxHeap PriorityQueue { a: Int, b: Int - b - a } /* Push elements into the heap */ maxHeap.offer(1) maxHeap.offer(3) maxHeap.offer(2) maxHeap.offer(5) maxHeap.offer(4) /* Get the heap top element */ var peek maxHeap.peek() // 5 /* Remove the heap top element */ // The removed elements will form a descending sequence peek maxHeap.poll() // 5 peek maxHeap.poll() // 4 peek maxHeap.poll() // 3 peek maxHeap.poll() // 2 peek maxHeap.poll() // 1 /* Get the heap size */ val size maxHeap.size /* Check if the heap is empty */ val isEmpty maxHeap.isEmpty() /* Build a heap from an input list */ minHeap PriorityQueue(mutableListOf(1, 3, 2, 5, 4))没有内置堆类的语言JavaScript / TypeScript// JavaScript does not provide a built-in Heap class需自行实现可参考 my_heap.js 与 my_heap.ts。Dart无内置堆类参考 en/codes/dart/chapter_heap/my_heap.dart。Ruby无内置堆类参考 en/codes/ruby/chapter_heap/my_heap.rb。C无内置堆类参考 en/codes/c/chapter_heap/my_heap.c以预分配数组 显式size字段实现其可运行测试见 my_heap_test.c。此外Python 版源码还配套了 pythontutor 代码可视化链接 对应的交互演示可在 pythontutor 目录 相关资源中查看逐行执行动画。堆的实现数组存储与索引映射以下以大顶堆为例进行实现讲解将其转换为小顶堆只需反转所有与大小比较有关的逻辑例如将 $\geq$ 改为 $\leq$有兴趣的读者可以自行完成。堆的存储与表示如二叉树章节所述完全二叉树非常适合用数组表示。由于堆是特殊的完全二叉树因此可以用数组来存储堆。用数组表示二叉树时数组元素代表节点的值数组索引代表节点在二叉树中的位置父子关系通过索引映射公式来表达。如下图所示给定索引 $i$其左子节点索引为 $2i 1$右子节点索引为 $2i 2$父节点索引为 $(i - 1) / 2$向下取整。当索引越界时表示空节点或该节点不存在。可以将索引映射公式封装为函数见各语言my_heap文件中的parent/left/rightdef left(self, i: int) - int: Get index of left child node return 2 * i 1 def right(self, i: int) - int: Get index of right child node return 2 * i 2 def parent(self, i: int) - int: Get index of parent node return (i - 1) // 2 # Floor division def swap(self, i: int, j: int): Swap elements self.max_heap[i], self.max_heap[j] self.max_heap[j], self.max_heap[i]完整实现见 en/codes/python/chapter_heap/my_heap.py在 C 语言实现 中则用预分配数组int data[MAX_SIZE]并配合int size记录实际元素数MAX_SIZE取 5000以避免动态扩容。Swift、C#、Go、Rust、Java、C、Kotlin、JS/TS 等语言的等价实现分别位于 en/codes/ 下各语言目录的chapter_heap/my_heap.*文件中。访问堆顶元素堆顶元素即二叉树的根节点也就是列表中的首个元素peek复杂度 $O(1)$def peek(self) - int: Access top element return self.max_heap[0]元素入堆push / sift up给定元素val首先将其添加至堆底。插入后由于val可能大于堆中的其他元素堆的性质可能被破坏因此需要沿从插入节点到根节点的路径修复堆这一操作被称为堆化heapify。从被插入节点开始自底向上执行堆化将插入节点与其父节点比较若插入节点更大则交换二者并持续自底向上执行直至越过根节点或遇到无需交换的节点为止。下图为元素入堆的各步骤示意完整序列图见 heap.assets 目录下的heap_push_step1.png至heap_push_step9.pngpush 前9 8 6 6 7 5 2 1 4 3 6 2 push 7 → 节点先加在堆底 → 与其父节点比较并上浮 push 后9 8 7 6 7 5 2 1 4 3 6 2 6示意图仅示意以源码实际输出为准核心代码如下sift_up自底向上堆化def push(self, val: int): Element enters heap # Add node self.max_heap.append(val) # Heapify from bottom to top self.sift_up(self.size() - 1) def sift_up(self, i: int): Starting from node i, heapify from bottom to top while True: # Get parent node of node i p self.parent(i) # When crossing root node or node needs no repair, end heapify if p 0 or self.max_heap[i] self.max_heap[p]: break # Swap two nodes self.swap(i, p) # Loop upward heapify i p设堆共有 $n$ 个节点则树高为 $O(\log n)$堆化操作的循环次数至多为 $O(\log n)$因此元素入堆操作的时间复杂度为 $O(\log n)$。堆顶元素出堆pop / sift down堆顶元素是二叉树的根节点也就是列表的首个元素。若直接从列表中删除首个元素所有节点索引都会变化后续堆化将难以修复。为尽量减小元素索引的变动采用如下步骤交换堆顶元素与堆底元素即交换根节点与最右叶节点交换完成后将堆底从列表中删除注意由于已经交换实际删除的是原堆顶元素从根节点开始自顶向下执行堆化。下图为堆顶元素出堆的各步骤示意完整序列图见 heap.assets 目录下的heap_pop_step1.png至heap_pop_step10.pngpop 前9 8 7 6 7 5 2 1 4 3 6 2 6 步骤9 与末尾 6 交换 → 移除末尾 → 新根 6 与较大子节点下沉 pop 后8 7 6 6 7 5 2 1 4 3 6 2“自顶向下的堆化”方向与“自底向上的堆化”正好相反将根节点的值与它的两个子节点比较并与其最大的子节点交换然后循环该操作直到越过叶节点或遇到无需交换的节点。核心代码如下sift_down自顶向下堆化def pop(self) - int: Element exits heap # Handle empty case if self.is_empty(): raise IndexError(Heap is empty) # Swap root node with rightmost leaf node (swap first element with last element) self.swap(0, self.size() - 1) # Delete node val self.max_heap.pop() # Heapify from top to bottom self.sift_down(0) # Return top element return val def sift_down(self, i: int): Starting from node i, heapify from top to bottom while True: # Find node with largest value among i, l, r, denoted as ma l, r, ma self.left(i), self.right(i), i if l self.size() and self.max_heap[l] self.max_heap[ma]: ma l if r self.size() and self.max_heap[r] self.max_heap[ma]: ma r # If node i is largest or indices l, r are out of bounds, no need to continue heapify, break if ma i: break # Swap two nodes self.swap(i, ma) # Loop downward heapify i ma在 C 语言实现中还需注意空堆与满堆的边界保护my_heap.c 的pop在堆为空时打印heap is empty!并返回INT_MAXpush在堆满size MAX_SIZE时打印heap is full!并直接返回。与元素入堆操作类似堆顶元素出堆的时间复杂度同样为 $O(\log n)$。从数组建堆heapify 整体构造上述手写MaxHeap构造函数支持直接传入一个无序数组并在线性时间内建堆将数组元素原样放入堆存储后从最后一个非叶节点开始向前逐个执行sift_down跳过所有叶节点即可在 $O(n)$而非 $O(n\log n)$时间内完成堆化。对应源码见 my_heap.py 的__init__def __init__(self, nums: list[int]): Constructor, build heap based on input list # Add list elements to heap as is self.max_heap nums # Heapify all nodes except leaf nodes for i in range(self.parent(self.size() - 1), -1, -1): self.sift_down(i)heapq.heapify、C 以迭代器区间构造priority_queue、Rust 的BinaryHeap::from等内置建堆方式同样具备 $O(n)$ 复杂度。关于建堆复杂度推导与“为什么是 $O(n)$ 而非 $O(n\log n)$”的完整证明可阅读 build_heap.md。堆的典型应用场景优先队列堆通常是实现优先队列的首选数据结构入队与出队操作时间复杂度均为 $O(\log n)$建堆时间复杂度为 $O(n)$整体效率很高。堆排序给定一组数据可以先将其构建成堆再不断执行堆顶出堆操作得到有序数据。不过实际中通常采用更优雅的方式实现堆排序原地、不稳定、$O(n\log n)$详见堆排序章节。求解最大的 $k$ 个元素这是一个经典算法问题也是堆的典型应用例如微博热搜 Top 10、销量最高的 Top 10 商品等场景。通常做法是维护一个大小为 $k$ 的小顶堆堆顶即当前第 $k$ 大的元素新元素与堆顶比较即可在线性扫描中维护前 $k$ 大集合实现见 top_k.py完整讲解见 top_k.md。以上应用与堆的基础实现共同构成了本仓库堆章节chapter_heap 目录的完整学习链路先掌握定义与内置优先队列用法再深入数组实现与堆化原理最后在堆排序与 Top-K 实战中巩固运用。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考