堆 (数据结构)
维基百科，自由的百科全书
 |
本条目没有列出任何参考或来源。（2011年10月19日） |
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。 堆总是满足下列性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
目录 |
支持的基本操作 [编辑]
堆支持以下的基本:
- build:建立一个空堆；
- insert:向堆中插入一个新元素；
- update：将新元素提升使其符合堆的性质；
- get：获取当前堆顶元素的值；
- delete：删除堆顶元素；
- heapify：使删除堆顶元素的堆再次成为堆。
某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。
应用 [编辑]
堆排序 [编辑]
堆（通常是二叉堆）常用于排序。这种算法称作堆排序。
优先队列 [编辑]
最小堆常用于实现优先队列。
参见 [编辑]
|
||||||||||||||||||||
|
||||||||||||||||||||||||||
