堆積

「堆積」的各地常用名稱
中國大陸	堆
臺灣	堆積

堆積（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)$

某些堆積實現還支援其他的一些操作，如斐波那契堆積支援檢查一個堆積中是否存在某個元素。

範例代碼[編輯]

為將元素X插入堆積中，找到空閒位置，建立一個空穴，若滿足堆積序性（英文：heap order），則插入完成；否則將父節點元素裝入空穴，刪除該父節點元素，完成空穴上移。直至滿足堆積序性。這種策略叫做上濾（percolate up）。^[1]

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;
}

應用[編輯]

堆積排序[編輯]

堆積（通常是二叉堆積）常用於排序。這種演算法稱作堆積排序。

事件模擬[編輯]

主要運用堆積的排序以選擇優先。

優先權佇列[編輯]

在佇列中，排程程式反覆提取佇列中第一個作業並執行，因為實際情況中某些時間較短的任務將等待很長時間才能結束，或者某些不短小，但具有重要性的作業，同樣應當具有優先權。堆積即為解決此類問題設計的最佳數據結構。^[1]

戴克斯特拉演算法[編輯]

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

參考[編輯]

^ ^1.0 ^1.1 《數據結構與演算法分析》Mark Allen Weiss（美）第六章，優先佇列（堆積）。

參見[編輯]

[定义-1] 1.0 ^1.1 《數據結構與演算法分析》Mark Allen Weiss（美）第六章，優先佇列（堆積）。

[1]