首先是堆的概念。
堆就是完全二叉树，即叶子节点只可能在最大的两层上出现，且只允许最大的一层上有空缺，且空缺的节点必须是从左到右连续的。
堆可以分为大根堆和小根堆，其中大根堆就是每个子树的根节点都是最大的，而小根堆中的每个子树都是根节点中最小的。
堆排序中可以利用数组来实现大根堆，父节点在i位置上，则左节点在2*i+1位置上，右节点在2*i+2的位置上。
堆排序的思想就是利用堆，将数组中的所有元素插入大根堆中，可以保证大根堆的顶部元素一定是最大的，然后将最后一个元素和首元素进行交换，使堆的大小减一，保证数组的最后一个元素是最大的元素。不断循环就可以使数组有序，且时间复杂度在O（logn），空间复杂度为O（1）。
void Swap(int &a,int &b) { if(a==b) return; a=a^b; b=a^b; a=a^b; } void HeapSort(int* &arr,int n) { if(arr==NULL || n<2) return; for(int i=0;i<n;i++) { HeapInsert(arr,i); } int heapsize=n; Swap(arr[0],arr[--heapsize]); while(heapsize) { Heapfy(arr,0,heapsize); Swap(arr[0],arr[--heapsize]); } } void HeapInsert(int* &arr,int index) { while(arr[index]>arr[(index-1)/2]) { Swap(arr[index],arr[(index-1)/2]); index=(index-1)/2; } } void Heapfy(int* &arr,int index,int heapsize) { int left=index*2+1; while(left<heapsize) { int largest= left + 1 < heapsize && arr[left+1]>arr[left] ? left+1 :left; //左右孩子比较大小 largest= arr[largest] > arr[index] ? largest :index; //大的孩子和父节点比较大小 if(largest == index) break; Swap(arr[largest],arr[index]); index=largest; left= index *2+1; } }
原文：https://www.cnblogs.com/RainzzZ/p/12761736.html