#define _CRT_SECURE_NO_WARNINGS
#include<iostream>template<class T>
void swap(T& a,T& b)
{T tmp = std::move(a);a = std::move(b);b = std::move(tmp);
}//建大堆
void AdjustDown(int* arr,int size,int root)//这里是向下调整算法。
{int parent = root;int child = root * 2 + 1;while (child<size){if (child+1 <size &&arr[child]<arr[child+1]){child += 1;//两个孩子节点较大的；}if (arr[child] > arr[parent]){swap(arr[child],arr[parent]);parent = child;child = child * 2 + 1;}else{break;}}}//1.升序排序建大根堆，降序排序建小根堆。这里默认是升序排序，所以建大堆。
//2.将堆顶元素与末尾元素进行交换，将堆顶的最大元素沉到数组末尾。
//3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤直到整个序列有序。void Heap_Sort(int* arr, int size)
{//1.先建堆int root = (size - 1 - 1) / 2;//最后一个叶子结点的父节点。for (int i=root;i>=0;--i){AdjustDown(arr, size, i);//向下调整}//2.排序for (int i=size;i>1;--i)//i不用等于1，只剩一个元素那么就不用再排序了，这个时候已经有序了；{swap(arr[0],arr[i-1]);//堆顶元素与最后一个节点元素交换AdjustDown(arr,i-1,0);//现在只需对i-1个元素重新调整建堆。}}int main()
{int arr[] = {10,88,92,46,32,55,53,21,32,77};int size = sizeof(arr) / sizeof(int);Heap_Sort(arr,size);for (auto& e:arr){std::cout<<e<<std::endl;}return 0;
}
