歡迎光臨
每天分享高質量文章

漫畫:什麼是堆排序?

(點擊上方公眾號,可快速關註)


來源:程式員小灰


在上一篇漫畫中,小灰介紹了 二叉堆 這樣一種強大的資料結構:


漫畫:什麼是二叉堆?


那麼,這個二叉堆怎樣來使用呢?我們這一期將會詳細講述。


讓我們回顧一下二叉堆和最大堆的特性:


1.二叉堆本質上是一種完全二叉樹

2.最大堆的堆頂是整個堆中的最大元素


當我們刪除一個最大堆的堆頂(並不是完全刪除,而是替換到最後面),經過自我調節,第二大的元素就會被交換上來,成為最大堆的新堆頂。




正如上圖所示,當我們刪除值為10的堆頂節點,經過調節,值為9的新節點就會頂替上來;當我們刪除值為9的堆頂節點,經過調節,值為8的新節點就會頂替上來…….


由於二叉堆的這個特性,我們每一次刪除舊堆頂,調整後的新堆頂都是大小僅次於舊堆頂的節點。那麼我們只要反覆刪除堆頂,反覆調節二叉堆,所得到的集合就成為了一個有序集合,過程如下:


刪除節點9,節點8成為新堆頂:




刪除節點8,節點7成為新堆頂:



刪除節點7,節點6成為新堆頂:



刪除節點6,節點5成為新堆頂:


刪除節點5,節點4成為新堆頂:


刪除節點4,節點3成為新堆頂:


刪除節點3,節點2成為新堆頂:


到此為止,我們原本的最大堆已經變成了一個從小到大的有序集合。之前說過二叉堆實際儲存在陣列當中,陣列中的元素排列如下:


由此,我們可以歸納出堆排序演算法的步驟:


1. 把無序陣列構建成二叉堆。

2. 迴圈刪除堆頂元素,移到集合尾部,調節堆產生新的堆頂。




public class HeapSort {

  1. /**

  2. * 下沉調整

  3. * @param array     待調整的堆

  4. * @param parentIndex    要下沉的父節點

  5. * @param parentIndex    堆的有效大小

  6. */

  7. public static void downAdjust(int[] array, int parentIndex, int length) {

  8.    // temp儲存父節點值,用於最後的賦值

  9.    int temp = array[parentIndex];

  10.    int childIndex = 2 * parentIndex + 1;

  11.    while (childIndex < length) {

  12.        // 如果有右孩子,且右孩子大於左孩子的值,則定位到右孩子

  13.        if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {

  14.            childIndex++;

  15.        }

  16.        // 如果父節點小於任何一個孩子的值,直接跳出

  17.        if (temp >= array[childIndex])

  18.            break;

  19.        //無需真正交換,單向賦值即可

  20.        array[parentIndex] = array[childIndex];

  21.        parentIndex = childIndex;

  22.        childIndex = 2 * childIndex + 1;

  23.    }

  24.    array[parentIndex] = temp;

  25. }


  26. /**

  27. * 堆排序

  28. * @param array     待調整的堆

  29. */

  30. public static void heapSort(int[] array) {

  31.    // 1.把無序陣列構建成二叉堆。

       for (int i = (array.length-2)/
    2; i >= 0; i--) {

  32.        downAdjust(array, i, array.length);

  33.    }

  34.    System.out.println(Arrays.toString(array));

  35.    // 2.迴圈刪除堆頂元素,移到集合尾部,調節堆產生新的堆頂。

  36.    for (int i = array.length - 1; i > 0; i--) {

  37.        // 最後一個元素和第一元素進行交換

  38.        int temp = array[i];

  39.        array[i] = array[0];

  40.        array[0] = temp;

  41.        // 下沉調整最大堆

  42.        downAdjust(array, 0, i);

  43.    }

  44. }


  45. public static void main(String[] args) {

  46.    int[] arr = new int[] {1,3,2,6,5,7,8,9,10,0};

  47.    heapSort(arr);

  48.    System.out.println(Arrays.toString(arr));

  49. }

}





二叉堆的節點下沉調整(downAdjust 方法)是堆排序演算法的基礎,這個調節操作本身的時間複雜度是多少呢?


假設二叉堆總共有n個元素,那麼下沉調整的最壞時間複雜度就等同於二叉堆的高度,也就是O(logn)


我們再來回顧一下堆排序演算法的步驟:


1. 把無序陣列構建成二叉堆。

2. 迴圈刪除堆頂元素,移到集合尾部,調節堆產生新的堆頂。


第一步,把無序陣列構建成二叉堆,需要進行n/2次迴圈。每次迴圈呼叫一次 downAdjust 方法,所以第一步的計算規模是  n/2 * logn,時間複雜度O(nlogn)


第二步,需要進行n-1次迴圈。每次迴圈呼叫一次 downAdjust 方法,所以第二步的計算規模是 (n-1) * logn ,時間複雜度 O(nlogn)


兩個步驟是併列關係,所以整體的時間複雜度同樣是 O(nlogn)










【關於投稿】


如果大家有原創好文投稿,請直接給公號發送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章鏈接

② 示例:
【投稿】
《不要自稱是程式員,我十多年的 IT 職場總結》:

http://blog.jobbole.com/94148/


③ 最後請附上您的個人簡介哈~



覺得本文有幫助?請分享給更多人

關註「演算法愛好者」,修煉編程內功

赞(0)

分享創造快樂

© 2020 知識星球   网站地图