heap_sort.cpp

// heap_sort.cpp
// -----------------------------------------------------------------
// Heap Sort（堆積排序）
//
// 原理：先把陣列建成最大堆（max-heap），
//       然後反覆把堆頂（最大值）換到尾端、縮小堆、再下濾（sift down）。
//
// 時間複雜度：最好 / 平均 / 最壞 都是 O(n log n)
//   - 建堆是 O(n)（自底向上 heapify）
//   - n 次取出堆頂各 O(log n)
// 空間複雜度：O(1)（原地）
// 穩定性：不穩定
// 特點：無最壞退化、常數空間，是 Intro Sort 的「保底」演算法。
//
// Compile: g++ -std=c++17 -O2 -Wall -o heap_sort heap_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 對 a[i] 在大小為 n 的堆中下濾
static void siftDown(vector<int>& a, int n, int i) {
    while (true) {
        int largest = i;
        int l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) break;
        swap(a[i], a[largest]);
        i = largest;
    }
}

void heapSort(vector<int>& a) {
    int n = (int)a.size();
    // 1. 自底向上建最大堆：從最後一個內部節點往前 sift down，O(n)
    for (int i = n / 2 - 1; i >= 0; --i)
        siftDown(a, n, i);
    // 2. 反覆把最大值換到尾端，縮小堆再下濾
    for (int end = n - 1; end > 0; --end) {
        swap(a[0], a[end]);
        siftDown(a, end, 0);
    }
}

static void printVec(const string& tag, const vector<int>& a) {
    cout << tag;
    for (int x : a) cout << x << " ";
    cout << "\n";
}

int main() {
    vector<vector<int>> tests = {
        {12, 11, 13, 5, 6, 7},
        {5, 2, 9, 1, 5, 6},
        {1, 2, 3, 4, 5},
        {5, 4, 3, 2, 1},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        heapSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}