Min-Heap

定义 Definition

最小堆：一种常见的堆（heap）数据结构，通常用完全二叉树（常用数组实现）表示，满足堆序性质：任一节点的键值都不大于其子节点的键值，因此最小值总在堆顶（根节点）。常用于实现优先队列、以及堆排序、Dijkstra 等算法中。

发音 Pronunciation (IPA)

/ˈmɪn hiːp/

例句 Examples

A min-heap lets you get the smallest item quickly.
最小堆可以让你快速取到最小的元素。

To keep the scheduler efficient, we stored incoming tasks in a min-heap so the next job with the earliest deadline could be extracted in (O(\log n)) time.
为了让调度器高效运行，我们把新任务存入最小堆，这样就能在 (O(\log n)) 时间内取出截止时间最早的下一个任务。

词源 Etymology

min- 来自 minimum（最小的）的缩写；heap 原义是“堆、堆积”，在计算机科学中引申为一种按特定规则组织元素的树形结构。min-heap 直译即“最小（元素在顶端）的堆”。

相关词 Related Words

• Binary Heap
• Heap
• Max-Heap
• Priority Queue
• Extract-Min
• Heapify
• Dijkstra

文学与经典著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，《算法导论》）：在“堆与优先队列”相关章节中系统介绍最小堆与 EXTRACT-MIN 等操作。
• The Algorithm Design Manual（Steven S. Skiena，《算法设计手册》）：在数据结构与图算法讨论中频繁使用最小堆作为优先队列实现。
• Algorithms（Robert Sedgewick & Kevin Wayne，《算法（第4版）》）：在优先队列、图最短路径等内容中讲解并应用最小堆/二叉堆思想。