堆排序的核心是什么？
借助堆數(shù)據(jù)結(jié)構(gòu)，不斷輸出當(dāng)前堆頂元素（小根堆），每次堆頂離開當(dāng)前堆后，對剩余元素重新調(diào)整成堆，直到堆中只剩下一個元素；元素的輸出序列可轉(zhuǎn)換成元素的有序序列。

堆排序的步驟：
1. 當(dāng)一個節(jié)點被插入時，將該節(jié)點放在堆的末尾（這是為了保證堆是完全二叉樹）；
2. 然后將該節(jié)點與它的父節(jié)點比較，看該節(jié)點是否大于（或小于）其父節(jié)點，即判斷當(dāng)前的堆是否滿足堆序；
3. 如果不滿足，則將該節(jié)點與其父節(jié)點交換。再將該節(jié)點與其新的父節(jié)點做比較，依此類推，直到該節(jié)點不再需要與其父節(jié)點交換為止；
4. （即滿足堆序時停止）當(dāng)一個根節(jié)點被彈出（即被從堆中刪除）時，將堆最尾部的節(jié)點移動到頭結(jié)點的位置，然后將該節(jié)點不斷與其子節(jié)點比較，如果不符合堆序則交換，直到符合堆序為止。

下濾
當(dāng)堆底插入新元素時，如果新插入元素大于其父元素，堆序性被破壞，此時應(yīng)將插入元素與其父元素交換位置，直至滿足堆序性。

上濾
當(dāng)堆頂元素被刪除時，將堆底元素插入堆頂，當(dāng)插入元素小于子節(jié)點時，堆的堆序性被破壞，將插入元素與子節(jié)點的較大值交換順序。
繼續(xù)此操作直至該堆成為一個合法的大根堆為止。

在插入堆的時候，使用下濾維護堆序性，在刪除堆頂元素時，使用上濾來維護堆序性。

將一個數(shù)組轉(zhuǎn)化為大根堆或小根堆的思路是，從最后一個非葉子節(jié)點向根節(jié)點出發(fā)，依次進行下濾，這樣就可以得到一個滿足堆排序的數(shù)組。
然后每次彈出根元素后進行上濾操作維護堆序性，就可以實現(xiàn)堆排序

heapq類實現(xiàn)的是小根堆?？梢詫⒚總€值乘以-1從而可以用該類實現(xiàn)大根堆