堆

“堆”的各地常用名称
“堆”的各地常用名称
中国大陆	堆
台湾	堆积

堆（Heap）是计算机科学中的一种特别的完全二叉树。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有父节点（parent node）。

堆始于J. W. J. Williams（英语：J. W. J. Williams）在1964年发表的堆排序（heap sort），当时他提出了二叉堆树作为此算法的数据结构。

性质

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

任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆有许多种高级类型包含了适合制作双端队列的最大—最小堆及制作优先权队列的斐波那契堆等。

支持的基本操作

操作	描述	时间复杂度
build	采用罗伯特·弗洛伊德提出的较快方式建立堆	$O(n)$
insert	向堆中插入一个新元素	$O(\log n)$
update	将新元素提升使其符合堆的性质	$O(\log n)$
get	获取当前堆顶元素的值	$O(1)$
delete	删除堆顶元素	$O(\log n)$
heapify	使删除堆顶元素的堆再次成为堆	$O(\log n)$

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

堆的在线可视化页面提供了多种堆操作的可视化演示。可以通过界面上的切换按钮在大根堆和小根堆之间自由切换，切换时系统会自动重新构建整个堆结构。^[1]

可以在输入框中输入数字并点击"插入节点"按钮，就能观察新节点如何通过上浮（heapify up）操作找到其正确位置。

当点击"删除根节点"按钮时，可以看到堆顶元素被移除，以及最后一个节点如何通过下沉（heapify down）操作重建堆的平衡。删除的节点会在右侧短暂显示，随后会消失。

此外，该页面还提供了随机初始化功能，可以快速生成一个包含10到50个随机数值的新堆，方便进行各种测试和观察。

示例代码

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

void Insert( ElementType X, PriorityQueue H ) {
    int i;
    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，删除最小元，即二叉树的根或父节点。删除该节点元素后，队列最后一个元素必须移动到堆得某个位置，使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。

ElementType DeleteMin(PriorityQueue H) {
    int i, Child;
    ElementType MinElement, LastElement;
    if (IsEmpty(H)) {
        printf("Queue is empty.\n");
        return H->Elements[0];
    }
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];
    for (i = 1; i * 2 <= H->Size; i = Child) {
        // Find smaller child.
        Child = i * 2;
        if (Child != H->Size && H->Elements[Child + 1]
                <  H->Elements[Child])
            Child++;
        // Percolate one level.
        if (LastElement > H->Elements[Child])
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement;
    return MinElement;
}

应用

堆排序

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

事件模拟

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

优先权队列

在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的最佳数据结构。^[2]

戴克斯特拉算法

在戴克斯特拉算法中使用斐波那契堆或二元堆可使得队列的操作更为快速。

参考

^ 堆的在线可视化页面: 支持堆操作的可视化演示
^ ^2.0 ^2.1 《数据结构与算法分析》Mark Allen Weiss（美）第六章，优先队列（堆）。

参见

[1] 堆的在线可视化页面: 支持堆操作的可视化演示

[定义-2] 2.0 ^2.1 《数据结构与算法分析》Mark Allen Weiss（美）第六章，优先队列（堆）。

[1]

[2]