堆这种数据结构应用场景很多，最经典的莫过于堆排序。堆排序（HeapSort）是一种原地的、时间复杂度为O(nlogn)的排序算法。我们今天就来分析一下堆排序。
一、算法描述
堆排序按照从小到大的顺序进行排序的步骤如下：
1.将长度为n的序列构造成为一个大顶堆；
2.将根结点与序列最后一个结点进行交换，此时最后一个结点就是该序列的最大值；
3.将剩余的n-1个结点再次构造成为一个大顶堆；
4.重复步骤2、3，直到构造成一个完全有序的序列。
堆需要满足两个条件：
是一颗完全二叉树（CompleteBinaryTree）
堆上面的每一个节点都必须满足父结点的值大于等于子结点的值或者父结点的值小于等于子结点的值。parent=childrenorparent=children
二、完全二叉树
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
举个栗子：
满二叉树：
深度为k且有2^k-1个结点的二叉树称为满二叉树。
完全二叉树：
树中含有n个结点和满二叉树中编号为1至n的结点一一对应。
三、大顶堆和小顶堆
堆又分为大顶堆和小顶堆。
大顶堆：
是完全二叉树且每个父节点都大于等于它的两个子结点时，就称为大顶堆。
公式定义：
arr[i]=arr[2i+1]
arr[i]=arr[2i+2]
小顶堆：
是完全二叉树且每个父节点都小于等于它的两个子结点时，就称为小顶堆。
公式定义：
arr[i]=arr[2i+1]
arr[i]=arr[2i+2]
四、堆的性质
例如我们已经有一个大顶堆，那么这个大顶堆具有哪些特征呢？
将其映射为数组：
intarr[]={12,10,9,6,7,8,5,3,2}
我们假设结点6的位置为i=3。那么我们可以求出，他的父节点和两个子结点。
Parent=(i-1)/2，等于位置为1的结点10。
C1=2i+1，等于位置为7的结点3。
C2=2i+2，等于位置为8的结点2。
五、图解堆排序算法
我们以inttree[]={6,10,3,8,5,12,7,2,9}为例，对堆排序的执行过程进行图解。
第一步：通过原始序列构造一个大顶堆（升序采用大顶堆，降序采用小顶堆）。
1.先通过序列通过从上到下从左往右的顺序构造一个完全二叉树。
2.对第三层的父节点和第四层的子结点进行调整，其中粉红色代表发生交换的结点。使得其父节点大于两个子结点。
即也是从最后1个非叶子结点开始(8-1)/2=3,也就是从8开始进行从左到右从下到上进行调整。
[8,2,9]中，9最大，交换8和9。
3.对第二层父节点和第三层子结点进行调整。
[10,9,5]中，10最大，不交换。
[3,12,7]中，12最大，交换3和12。
4.对第一层父节点和第二层子结点进行调整。
[6,10,12]中，12最大，交换6和12。
这时，上面操作导致[6,3,7]不是一个大顶堆，继续调整。
[6,3,7]中，7最大，交换6和7。
至此，大顶堆构建完成。
第二步：将根结点调整到最后一个位置，使末尾元素最大。然后对剩下元素继续调整堆，根结点调整到最后一个位置，得到第二大元素。如此反复进行交换、重够、交换。
1.将根节点元素12跟8交换。
2.重新调整结构，使其继续满足堆定义。
3.将根节点元素10跟2交换。
4.重新调整结构，使其继续满足堆定义。
这样一直交换、重够、交换下去.......
5.最后一次将根节点元素3跟2交换。
这样所有元素就达到了有序状态。
六、算法实现
第一步：构建大顶堆
#includestdio.hvoidswap(intarr[],inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}voidheapify(inttree[],intn,inti){if(i=n){return;}intc1=2*i+1;intc2=2*i+2;intmax=i;if(c1ntree[c1]tree[max]){max=c1;}if(c2ntree[c2]tree[max]){max=c2;}if(max!=i){swap(tree,max,i);heapify(tree,n,max);}}voidbuild_heap(inttree[],intn){intlast_node=n-1;intparent=(last_node-1)/2;for(inti=parent;i=0;i--){heapify(tree,n,i);}}voidheap_sort(inttree[],intn){build_heap(tree,n);for(inti=n-1;i=0;i--){swap(tree,i,0);heapify(tree,i,0);}}intmain(){inttree[]={6,10,3,9,5,12,7,2,8};intn=9;build_heap(tree,9);//heap_sort(tree,9);for(inti=0;in;i++){printf("%d\n",tree[i]);}return0;}
输出：
我们将它画出来康康：
看是不是一颗大顶堆？那必须是呀。
第二步：排序
#includestdio.hvoidswap(intarr[],inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}voidheapify(inttree[],intn,inti){if(i=n){return;}intc1=2*i+1;intc2=2*i+2;intmax=i;if(c1ntree[c1]tree[max]){max=c1;}if(c2ntree[c2]tree[max]){max=c2;}if(max!=i){swap(tree,max,i);heapify(tree,n,max);}}voidbuild_heap(inttree[],intn){intlast_node=n-1;intparent=(last_node-1)/2;for(inti=parent;i=0;i--){heapify(tree,n,i);}}voidheap_sort(inttree[],intn){build_heap(tree,n);for(inti=n-1;i=0;i--){swap(tree,i,0);heapify(tree,i,0);}}intmain(){inttree[]={6,10,3,9,5,12,7,2,8};intn=9;//build_heap(tree,9);heap_sort(tree,9);for(inti=0;in;i++){printf("%d\n",tree[i]);}return0;}
输出：
我们将它画出来康康：
就这样我们就完成堆排序啦！开不开森。
六、算法分析
时间复杂度：堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是O(n)，排序过程的时间复杂度是O(nlogn)，所以，堆排序整体的时间复杂度是O(nlogn)。
空间复杂度：因为堆排序是就地排序，空间复杂度为常数：O(1)
稳定性：不稳定。因为在堆的调整过程中，元素进行比较和交换所走的是该结点到叶子结点的一条路径，因此对于相同的元素就可能出现排在后面的元素被交换到前面来的情况。
七、适用场景
堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。
*声明：本文于网络整理，版权归原作者所有，如来源信息有误或侵犯权益，请联系我们删除或授权事宜。