根据实现的MaxHeap类，实现堆排序很简单：将元素逐步insert进入堆，然后再extract_max逐个取出即可。当然，这个建堆的平均时间复杂度是O(n*log2_n)代码如下：
template <typename T> void heap_sort1(T arr[], int n) { MaxHeap<T> max_heap = MaxHeap<T>(n); for(int i = 0; i < n; i++) { max_heap.insert(arr[i]); } for(int i = n -1; i >= 0; i--) { arr[i] = max_heap.extract_max(); } }仔细观察前面实现的构造函数，构造函数可以传入数组参数。
// 将数组构造成堆：heapify MaxHeap(Item arr[], int n) { this->data = new Item[n+1]; this->capacity = n; this->count = n; for(int i = 0; i < n; i++) { this->data[i + 1] = arr[i]; } for(int i = n/2; i >= 1; i--) { this->shift_down(i); } }过程叫做heapify,实现思路如下：
将数组的值逐步复制到this->data
从第一个非叶子节点开始，执行shift_down
重复第 2 步，直到堆顶元素
这种建堆方法的时间复杂度是: O(n)。因此, 编写heap_sort2函数：
// 建堆复杂度：O(N) template <typename T> void heap_sort2(T arr[], int n) { MaxHeap<T> max_heap = MaxHeap<T>(arr, n); for(int i = n -1; i >= 0; i--) { arr[i] = max_heap.extract_max(); } }上面阐述的两种排序方法，借助实现的最大堆这个类，都需要在类中开辟this->data，空间复杂度为O(n)。其实，借助shift_down可以实现原地堆排序，代码如下：
// 这里的 swap 操作并没有优化 // 请对比 MaxHeap 中的 shift_down 函数 template <typename T> void __shift_down(T arr[], int n, int k) { while( 2*k + 1 < n) { int j = 2 * k + 1; if( j + 1 < n && arr[j + 1] > arr[j]) { j += 1; } if(arr[k] >= arr[j]) { break; } swap(arr[k], arr[j]); k = j; } } // 原地堆排序 template <typename T> void heap_sort3(T arr[], int n) { for(int i = (n -1)/2; i>=0; i--) { __shift_down(arr, n, i); } for(int i = n-1; i > 0; i--) { swap(arr[0], arr[i]); __shift_down(arr, i, 0); } } 5. 测试 5.1 测试MaxHeap类测试代码如下：
#include <iostream> #include <ctime> #include <algorithm> #include "MaxHeap.h" #include "SortHelper.h" #define HEAP_CAPACITY 10 #define MAX_NUM 100 using namespace std; int main() { MaxHeap<int> max_heap = MaxHeap<int>(HEAP_CAPACITY); srand(time(NULL)); for(int i = 0; i < HEAP_CAPACITY + 5; i++) { // 容量超出初始化时的容量。测试：自动 max_heap.insert(rand() % MAX_NUM); } while( !max_heap.is_empty() ) { cout<< max_heap.extract_max() << " "; // 控制台输出数据是从大到小 } cout<<endl; return 0; } 5.2 测试堆排序借助前几篇文章的SortHelper.h封装的测试函数：
#include <iostream> #include <ctime> #include <algorithm> #include "MaxHeap.h" #include "SortHelper.h" #define HEAP_CAPACITY 10 #define MAX_NUM 100 using namespace std; int main() { int n = 100000; int* arr = SortTestHelper::generateRandomArray<int>(n, 0, n); int* brr = SortTestHelper::copyArray<int>(arr, n); int* crr = SortTestHelper::copyArray<int>(arr, n); SortTestHelper::testSort<int>(arr, n, heap_sort1<int>, "first heap_sort"); SortTestHelper::testSort<int>(brr, n, heap_sort2<int>, "second heap_sort"); SortTestHelper::testSort<int>(crr, n, heap_sort3<int>, "third heap_sort"); delete[] arr; delete[] brr; delete[] crr; return 0; }