排序與搜尋
堆積排序
堆積排序靠的是一個巧妙的資料結構：二元堆積。它先把陣列重排成一個大頂堆積——一種每個父節點都不小於其子節點的形狀，於是最大的元素浮到了頂端（陣列的最前面）。接著它反覆把這個頂端元素交換到末尾、把堆積的規模縮小一個，再讓堆積自我修復——每一輪都剝下當前剩餘的最大元素，直到陣列排好序。
妙處在於這個堆積就住在同一個陣列裡，用索引算術（位置 i 的子節點在 2i+1 和 2i+2）代替指標。建堆積耗時 O(n)，而 n 次取最大值的每一步都要花 O(log n) 把新的根下沉回它該在的層級——也就是堆積的高度。
相乘就得到最好、平均、最壞情況下都一樣的 O(n log n) 時間——堆積排序和合併排序一樣，沒有「壞輸入」。更好的是，它原地排序，只需 O(1) 額外空間，這一點強過合併排序。它的弱點是不穩定，而且它跳躍、分散的記憶體存取不如快速排序對快取友善，所以實務中通常稍慢一點。它的長處是作為最壞情況安全的兜底方案——這正是內省排序在快排遞迴過深時改用堆積排序的原因。
void heapsort(std::vector<int>& a) {
std::make_heap(a.begin(), a.end()); // build max-heap, O(n)
for (auto end = a.end(); end != a.begin(); --end)
std::pop_heap(a.begin(), end); // move max to the back, O(log n)
} // array is now sorted ascendingn 次取出 × 每次 O(log n) 的下沉 = O(n log n)，原地排序，額外空間 O(1)。
堆積排序和合併排序都保證 O(n log n)；堆積排序在空間上勝出（O(1) 原地，對比 O(n)），但在穩定性上落敗（堆積排序不穩定，合併排序穩定）。C++ 把底層機制暴露為 std::make_heap、std::push_heap 和 std::pop_heap。
又稱
另見