## 堆排序 1. 先n个元素的无序序列，构建成大顶堆 2. 将根节点与最后一个元素交换位置，（将最大元素"沉"到数组末端） 3. 交换过后可能不再满足大顶堆的条件，所以需要将剩下的n-1个元素重新构建成大顶堆 4. 重复第二步、第三步直到整个数组排序完成 ``` void shiftDown(vector<int>& data, int k, int n) { while (2 * k + 1 < n) { int max = 2 * k + 1; if (max + 1 < n && data[max + 1] > data[max]) max++; if (data[k] > data[max]) break; swap(data[k], data[max]); k = max; } } // 大顶堆思想 void heapSort(vector<int>& data) { // build maxHeap for (int i = data.size() / 2 - 1; i >= 0; i--) shiftDown(data, i, data.size()); for (int i = data.size() - 1; i > 0; i--) { swap(data[0], data[i]); shiftDown(data, 0, i); } } ``` ```cpp /** * 堆排序 * parent = (i-1)/2 * left = i*2+1 * right = i*2+2 */ void heapify(vector<int>& data, int i, int n) { int max = i; int left = i * 2 + 1; int right = i * 2 + 2; if (left < n && data[max] < data[left]) { max = left; } if (right < n && data[max] < data[right]) { max = right; } if (max != i) { swap(data[i], data[max]); heapify(data, max, n); } } void build_heap(vector<int>& data) { int n = data.size(); int last_node = n - 1; for (int i = (last_node - 1) / 2; i >= 0; i--) { heapify(data, i, n); } } void heap_sort(vector<int>& data) { build_heap(data); for (int i = data.size() - 1; i > 0; i--) { swap(data[0], data[i]); heapify(data, 0, i); } } ```