一、定義

借助堆結(jié)構(gòu)實現(xiàn)的排序算法被稱為堆排序。

二、過程說明

1、建堆

（1）方法1

原地建堆，對于數(shù)組來說，從前往后；對于樹來說，從下向上。

將數(shù)組的第一個元素作為堆頂，第二個元素做向堆中插入數(shù)據(jù)的操作，即：從下向上堆化。直至所有的元素均完成所有插入操作，此時堆就建立完成了。

（2）方法2

原地建堆，對于數(shù)組來說，從后往前；對于樹來說，從上向下。

從數(shù)組倒數(shù)第一個非葉子節(jié)點向下進行堆化，之后是倒數(shù)第二個非葉子節(jié)點向下堆化，直至堆化到數(shù)組第一個節(jié)點，從而完成堆的建立。

（3）方法 2 和方法 1 的區(qū)別

方法 2 默認(rèn)數(shù)組開始時已經(jīng)是一顆樹了，但是不是堆結(jié)構(gòu)。之后的操作就是不斷比較交換，使得該樹滿足堆結(jié)構(gòu)。

方法 1 則從 0? 開始建堆，當(dāng)樹建好時，就是一顆標(biāo)準(zhǔn)的堆了。

（4）時間復(fù)雜度

這里說下方法 2 的時間復(fù)雜度。實際上真正進行堆化的節(jié)點為非葉子節(jié)點，并且是從上到下進行堆化。每個節(jié)點堆化的時間復(fù)雜度實際上是該節(jié)點的高度，總結(jié)如下圖所示：

經(jīng)過下圖推算，得出時間復(fù)雜度為 O(n) 。

?

2、排序

堆建完之后排序就很簡單了，因為此時的堆頂已經(jīng)是最大值（最小值）了，取出該值放到葉子節(jié)點的位置，原本葉子節(jié)點位置的數(shù)值移動到堆頂點，在進行一次從上到下的堆化，重新得到堆頂是第 2 大（小）的數(shù)。經(jīng)過多次堆化，就能得到從大到小或者從小到大的數(shù)據(jù)了。

排序階段的時間復(fù)雜度為 O(nlogn)，因為每次堆化時都是將葉子節(jié)點放到頂點然后從上到下堆化，堆化一次就相當(dāng)于比較 logn 次，logn 為樹的高度，需要比較 n 次，所以時間復(fù)雜度為 O(nlogn) 。

由于建堆 + 排序的時間復(fù)雜度為 O(n) + O(nlogn)，省略之后時間復(fù)雜度為 O(nlogn) 。

三、總結(jié)

由于堆排序的過程中，需要輪著將數(shù)據(jù)放到堆頂點進行堆化，導(dǎo)致該排序不是穩(wěn)定性排序。

同時由于整個過程只需要在本數(shù)組內(nèi)就能完成整個過程，需要其他內(nèi)存很少，故堆排序時原地排序。?

算法種類	時間復(fù)雜度	空間復(fù)雜度	原地排序	穩(wěn)定性排序
堆排序	O(nlogn)	O(n)	√	×

?

參考：極客時間《數(shù)據(jù)結(jié)構(gòu)與算法之美》王爭

這門課真心推薦，內(nèi)容很經(jīng)典、栗子很形象，里面還包含了很多面試題目。真是居家旅行必備良藥。

?

（SAW：Game Over！）

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法 / 排序算法 / 堆排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。