逻辑定义

n个元素序列{k 1 ,k 2 ...k i ...k n },当且仅当满足下列关系时称之为堆： (k i <= k 2i ,k i = k 2i ,k i >= k 2i+1 ), (i = 1,2,3,4...n/2)

性质

堆的实现通过构造 二叉堆 （binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。

任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（ 堆序性 ）。

堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

将根节点最大的堆叫做 最大堆 或 大根堆 ，根节点最小的堆叫做 最小堆 或 小根堆 。常见的堆有二叉堆、斐波那契堆等。

支持的基本操作

某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。

例程

为将元素X插入堆中，找到空闲位置，创建一个空穴，若满足 堆序性 （英文： heap order ），则插入完成；否则将父节点元素装入空穴，删除该父节点元素，完成空穴上移。直至满足堆序性。这种策略叫做 上滤 （percolate up）。

voidInsert(ElementTypeX,PriorityQueueH){inti;if(IsFull(H)){printf("Queue is full.\n");return;}for(i=++H->Size;H->Element[i/2]>X;i/=2)H->Elements[i]=H->Elements[i/2];H->Elements[i]=X;}

以上是插入到一个二叉堆的过程。

DeleteMin ，删除最小元，即二叉树的根或父节点。删除该节点元素后，队列最后一个元素必须移动到堆得某个位置，使得堆仍然满足堆序性质。这种向下替换元素的过程叫作 下滤 。

ElementTypeDeleteMin(PriorityQueueH){inti,Child;ElementTypeMinElement,LastElement;if(IsEmpty(H)){printf("Queue is empty.\n");returnH->Elements[0];}MinElement=H->Elements[1];LastElement=H->Elements[H->Size--];for(i=1;i*2Size;i=Child){/* Find smaller child. */Child=i*2;if(Child!=H->Size&&H->Elements[Child+1]Elements[Child])Child++;/* Percolate one level. */if(LastElement>H->Elements[Child])H->Elements[i]=H->Elements[Child];elsebreak;}H->Elements[i]=LastElement;returnMinElement;}

应用

堆排序

堆（通常是二叉堆）常用于排序。这种算法称作堆排序。

事件模拟

主要运用堆的排序以选择优先。

参见

二叉堆

二项式堆

最大-最小堆

斐波纳契堆

数据结构

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。