小序：什么是堆？
先了解一下什么是堆，堆是計(jì)算機(jī)科學(xué)中的一種特別的樹狀數(shù)據(jù)結(jié)構(gòu),堆總是一棵完全二叉樹,它總是滿足下列性質(zhì):
性質(zhì)1：堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值;
性質(zhì)2：堆總是一棵完全二叉樹。
? ? ? 堆的特征就是:給定堆中任意節(jié)點(diǎn)P和C,若P是C的母節(jié)點(diǎn),那么P的值會(huì)小于等于(或大于等于) C 的值”。將根節(jié)點(diǎn)最大的堆叫做最大堆、大頂堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆、小頂堆或小根堆，如下圖：。常見的堆有二叉堆、斐波那契堆等。
同時(shí)，我們對(duì)以上堆的這種邏輯結(jié)構(gòu)映射到數(shù)組中就是下面這個(gè)樣子：
我們用簡(jiǎn)單的公式定義一下大頂堆和小頂堆：
大頂堆：a[I] >= a[2i+1] && a[I] >= a[2i+2]
小頂堆：a[I] <= a[2i+1] && a[I] <= a[2i+2]
堆排序的思路？
首先我們先將數(shù)組序列構(gòu)造成一個(gè)大頂堆，此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換，此時(shí)末尾就為最大值。然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆，這樣會(huì)得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了。
堆排序
基于上面對(duì)堆的了解，相信你對(duì)堆排序會(huì)有了更好的認(rèn)識(shí)。堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序可以說(shuō)是一種利用堆的概念來(lái)排序的選擇排序。分為兩種方法：
大頂堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于升序排列；
小頂堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于降序排列；
堆排序的平均時(shí)間復(fù)雜度為 Ο(nlogn)。
1. 算法步驟
a、創(chuàng)建一個(gè)堆 H[0……n-1]；
b、把堆首（最大值）和堆尾互換；
c、把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；
d、重復(fù)步驟 2，直到堆的尺寸為 1。
2. 動(dòng)圖演示
3. 代碼實(shí)現(xiàn)
