#include<iostream> #include<vector> #include<stack> #include<algorithm> #include<string> #include<set> #include <functional> using namespace std; // 该函数用于构建大顶堆过程中自上而下的调整。 void MaxHeapFixDown(int a[], int i, int n) {
int j = 2 * i + 1; //当前元素的左子节点 int temp = a[i]; while (j<n) { if (j + 1 < n&&a[j] < a[j + 1]) ++j; // 此时a[j]是a[i]子节点的值大者 if (temp>a[j]) break; // 根节点已经不小于左右子节点,调整结束 else { a[i] = a[j]; i = j; j = 2 * i + 1; }// 子节点与根节点值进行交换后,那么该子节点的子树的大顶堆性质可能被破坏,因此继续向下进行调整 } a[i] = temp; } //堆排序 void HeapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) MaxHeapFixDown(a, i, n);//n个元素,最后一个非叶结点下标:n/2-1 。从最后一个非叶节点开始,由右至左,由下至上进行调整,最终构建一个大顶堆。 for (int i = n - 1; i >= 1; i--) { swap(a[i], a[0]); MaxHeapFixDown(a, 0, i); // 每次堆顶元素发生交换后,都可能破坏大顶堆的性质,因此从堆顶自上而下进行调整 } } int main() { int a[10] = { 4,8,7,0,3,5,9,1,1,8 }; HeapSort(a, 10); for (int i = 0; i < 10; i++) cout << a[i] << " "; cout << endl; return 0; }
参考链接:
https://www.cnblogs.com/chengxiao/p/6129630.html 这篇文章图画的非常好
https://blog.csdn.net/geekmanong/article/details/51209629 阿里的一道堆排序的简单题目