第12章 堆

来自维基百科

堆

堆（英语：heap) 亦被称为：优先队列（英语：priority queue），是中一类特殊的的统称。

堆通常是一个可以被看做一棵树的数组对象。在中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

逻辑定义

n个元素序列{k1,k2...ki...kn},当且仅当满足下列关系时称之为堆：

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

堆支持以下的基本操作:

build：建立一个空堆；

insert：向堆中插入一个新元素；

update：将新元素提升使其符合堆的性质；

get：获取当前堆顶元素的值；

delete：删除堆顶元素；

heapify：使删除堆顶元素的堆再次成为堆。