前言
堆 (二叉堆)是一种用于实现 优先队列 模型的数据结构,堆具有 堆序(heap order)性 , 每个节点的关键字都大于他的父节点的
只有根除外(没有父亲),也可以是都小于,子节点与父节点的关系决定了这个堆是最小堆还是最大堆,分别可以用来做升序和降序。使用优先队列理论上可以实现花费 O(N log N) 时间的排序。
方法
对一个数组进行升序的排列,可以先将数组中的 N 个元素建立一个二叉堆,这个操作花费 O(N) 时间,然后对该堆执行 N 此 DeleteMin 操作。堆中的数据按照从小到大依次离开堆,将这些元素 记录到第二个数组 中,最后再拷贝回来,以此得到了针对 N 个元素的排序。每个 DeleteMin 操作花费了 O(log N) 的时间,因此总开销是 O(N log N)。
注意到我们这里使用了一个额外的数组,空间开销加大了(将第二个数组数据拷贝回来只花费 O(N),不会显著增加时间消耗)。
虽然我们在程序中常常为了节省时间开销而消耗额外的空间,但在这个问题中有个方法可以避免。在每次 DeleteMin 操作之后,堆缩小了 1,,因此堆中最后的单元可以用来存放刚刚删去的元素。
DeleteMin(删除最小元)
这是在排序中重点需要的基本堆操作,要找到需要删除的元素很容易,难的是删除,当删除一个最小元时,在根节点产生了一个空穴,为了保证堆的性质,必需将堆中最后一个 元素 X 移动,如果它可以移动到空穴,那么 DeleteMin 完成,不过这一般不太可能,因此我们将空穴的两个子节点中较小的一个移入空穴,相当于把空穴往下移动了一层,不断重复这个过程直到 X 可以被放到空穴。这种策略被称作 下滤 。
最小堆与最大堆具有对称的性质,对于父节点大于子节点的最大堆,区别只是每次删除的是最大元,上移的是空穴子节点中较大的,与最小堆相反。
图片演示
代码
#define LeftChild(i) (2 * (i) + 1)
void PercDown(ElementType A[], int i, int N) {
int Child;
ElementType Tmp;
for (Tmp = A[i]; LeftChild(i) < N; i = Child) {Child = LeftChild(i);
if (Child != N - 1 && A[Child + 1] > A[Child])
Child++;
if (Tmp < A[Child])
A[i] = A[Child];
else
break;
}
A[i] = Tmp;
}
void Heapsort(ElementType A[], int N) {
int i;
for (i = N / 2; i >= 0; i--)
PercDown(A, i, N);
for (i = N - 1; i > 0; i--) {Swap(&A[0], &A[i]);
PercDown(A, 0, i);
}
}