???????堆的基本操作參考文章：[堆的基本操作](http://blog.csdn.net/u013074465/article/details/46741421) ?????? 對于小根堆來說，一般的思路是每次刪除最小值，執行N次刪除；每次將刪除的元素拷貝到一個新的數組，那么新數組將按照從小到大的順序排列。這里的主要問題是空間的：使用新數組，使存儲空間增加了一倍。 ?????? 一個技巧是：每次刪除一個堆元素，堆大小會減少1。那么位于堆最后的那個空間可以用來存放剛剛被刪除的元素。按照這種思路，不用額外的空間即可完成排序。 ????? 對小根堆，該方式排序完的數組是遞減的，那么，如果我們建立堆時用大根堆，則該方式得到的排序結果是遞增的。 ????? 堆排序中用到了下濾操作，因為堆排序其實就是堆刪除的一系列操作，而堆的刪除操作會下濾，參考[二叉堆的插入刪除等操作C++實現](http://blog.csdn.net/u013074465/article/details/42028473) ????? 在移動堆元素的時候（AdjustHeap函數中），用到了一個技巧來減少交換元素的次數，參考[插入排序和希爾排序](http://blog.csdn.net/u013074465/article/details/42043665)，這里不再贅述。 ~~~ /* （大根）堆排序，花費O(NlogN)。 */ template<typename T> void HeapSort(vector<T>& a) { int i; //先建立大根堆，該操作花費O(N) for (i = a.size() / 2; i >= 0; --i) { AdjustHeap(a, i, a.size()); } //將要刪除的元素放入堆末尾的空間（交換根元素和尾元素）， //這樣不需要額外的空間。 for (i = a.size() - 1; i > 0; --i) { T tmp = a[i]; a[i] = a[0]; a[0] = tmp; /* 每次刪除時，根元素與根末尾元素交換了，在位置0處下濾。 由于不斷從堆中刪除，因此堆大小不斷減小，為i */ AdjustHeap(a, 0, i); } } //該函數是堆操作中的下濾操作 template<typename T> void AdjustHeap(vector<T>&a, int pos, int n) { int pos_child; T tmp; for (tmp = a[pos]; (pos * 2 + 1) < n; pos = pos_child) { pos_child = 2 * pos + 1; if (pos_child != n -1 && a[pos_child] < a[pos_child + 1]) pos_child++; if (tmp < a[pos_child]) a[pos] = a[pos_child]; else break; } a[pos] = tmp; } //只是一個打印元素的函數 template<typename T> void PrintValue(vector<T>& a) { ?vector<T>::iterator iter = a.begin(); ?while (iter != a.end()) { ??? ?cout << *iter++ << " "; ?} ?cout << endl; } int main() { ?int value; ?vector<int> ivec; ?while (cin >> value) ??? ?ivec.push_back(value); ?HeapSort<int>(ivec); ?PrintValue(ivec); } ~~~