堆(Heap)是计算机科学中的一种特别的完全二叉树。若是满足以下特性,即可称为堆积:“给定堆积中任意节点P和C,若P是C的母节点,那么P的值会小于等于(或大于等于)C的值”。若母节点的值恒小于等于子节点的值,此堆积称为最小堆积(min heap);反之,若母节点的值恒大于等于子节点的值,此堆积称为最大堆积(max heap)。在堆积中最顶端的那一个节点,称作根节点(root node),根节点本身没有母节点(parent node)。
此条目需要补充更多来源。 (2024年8月11日) |
“堆积”的各地常用名称 | |
---|---|
中国大陆 | 堆 |
台湾 | 堆积 |
堆积始于J. W. J. Williams在1964年发表的堆积排序(heap sort),当时他提出了二元堆积树作为此演算法的资料结构。
性质
堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。这种数据结构具有以下性质。
- 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
- 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
支持的基本操作
某些堆实现还支持其他的一些操作,如斐波那契堆支持检查一个堆中是否存在某个元素。
示例代码
为将元素X插入堆中,找到空闲位置,建立一个空穴,若满足堆序性(英文:heap order),则插入完成;否则将父节点元素装入空穴,删除该父节点元素,完成空穴上移。直至满足堆序性。这种策略叫做上滤(percolate up)。[1]
以上是插入到一个二叉堆的过程。
DeleteMin
,删除最小元,即二叉树的根或父节点。删除该节点元素后,队列最后一个元素必须移动到堆得某个位置,使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。
应用
堆(通常是二叉堆)常用于排序。这种算法称作堆排序。
主要运用堆的排序以选择优先。
在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的最佳数据结构。[1]
参考
参见
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.