樹與層次結構
堆積
堆積是一種為一件事而調校的二元樹：隨時、即刻地知道最小（或最大）的元素。它不是搜尋樹——它給出的承諾弱得多，即堆積性質：每個父節點都小於等於它的子節點（最小堆），或大於等於它的子節點（最大堆）。對左右兄弟之間的大小則隻字不提，所以堆積只是部分有序——剛好夠把那個極值釘在根上。
兩個設計選擇讓它很快。其一，堆積是一棵完全二元樹：除可能的最後一層外，每一層都填滿，而最後一層從左到右依次填入。這種完美形狀意味著樹高始終約為 log n，絕不會退化。其二，正因為形狀如此規整，你根本不需要指標——把堆積直接存進一個普通陣列，索引 i 的兩個子節點落在 2i+1 和 2i+2，父節點在 (i-1)/2。整棵樹都隱含在這套索引算術裡。
插入時把新元素放到末尾，讓它一路向上冒泡、越過每個比它大的父節點；刪除堆頂時把最後一個元素換上來，再讓它向下沉到合適的層。每次修復都只走一條從根到葉的路徑，所以插入與取最小/取最大都是 O(log n)，而查看堆頂是 O(1)，因為它就是陣列的第一個槽位。這套組合正是優先佇列所需，而反覆讀出元素則是堆積排序的核心。
// min-heap stored in vector<int> h
void push(vector<int>& h, int x) {
h.push_back(x);
int i = h.size() - 1;
while (i > 0 && h[(i - 1) / 2] > h[i]) {
swap(h[i], h[(i - 1) / 2]); // sift up
i = (i - 1) / 2;
}
}陣列實作的堆積：插入先追加再上浮，是 O(log n) 操作。
堆積只能快速找到那一個最小或最大值——它無法以 O(log n) 搜尋任意的鍵；那是二元搜尋樹的活兒。
又稱
另見