堆排序，怎麼個堆法？

大家好，我是道哥。今天我們來聊重要的堆排序。堆排序在面試中是常考的內容，而且，堆也常用於處理各種海量數據面試題。

我們先看看究竟什麼是堆？以大頂堆爲例：

對於一棵完全二叉樹而言，當每個結點不小於其子結點時，便可稱之爲堆 (大頂堆)，比如：

原始的待排序的數組爲：

30, 20, 40, 10, 0, 60, 80, 70

其對應的完全二叉樹爲：

接下來，我們來圖解堆排序，並用程序來實現堆排序。在這個過程中，希望大家感受到堆之美。

圖解堆排序

一. 構建堆

第 1 步：

如上圖，最後一個非葉子結點是 10，發現 10 比 70 小，所以 70 必須上浮，得到的結果爲：

第 2 步：

如上圖，倒數第二個非葉子結點爲 40，在 40，60，80 這三個數中，80 最大，所以 80 必須上浮，得到的結果如下：

第 3 步：

如上圖，倒數第三個非葉子結點爲 20，而 20 比 70 小，所以 70 必須上浮，20 下沉後，發現比下面的 10 還大，所以沒有必要沉底，得到的結果爲：

第 4 步：

如上圖，倒數第四個非葉子結點爲 30，在 30，70，80 中，80 最大，所以 80 要上浮，30 下沉。然而，30 比 60 和 40 都小，所以要繼續下沉，得到的結果是：

到此爲止，可以看到，一個大頂堆已經形成，可以看到，最大的 80 已經被選擇出來了。

二. 調整堆

我們把堆頂的最大值 80 調整到最後，保存下來，得到的結果是：

接下來的工作就是對上面紅框中的的 7 個結點進行調整，使之形成新的堆。

很顯然，根據之前調整的過程可知，兩個藍色框中的結點，已經分別成堆了，所以這次的調整就簡單多了，直接瞄準待調整的 10 即可。

之前已經把 8 個結點調整成堆，那麼調整上面紅色框中的 7 個結點成堆便不在話下。於是，這 7 個結點中最大的 70 被調到了堆頂，如下：

80 是最大的值，放在最後。堆頂的 70 是第二大的值，放在倒數第二的位置，所以跟 40 進行交換，得到的結果爲：

可見，通過 2 次從堆頂摘下最大元素，分別把 80 和 70 選出來了。接下來，用相同的方法，把 60 選出來，依此循環，最後得到的二叉樹爲：

終於，實現了排序，這就是所謂的堆排序，其平均時間複雜度爲 O(N*logN), 比冒泡排序好多啦。

堆排序實現

接下來，我們用代碼來實現堆排序，如下：

#include<iostream>
using namespace std;
void print(int a[], int n)
{
  int i;
  for(i = 0; i < n; i++)
  {
    cout << a[i] << " ";
  }
  cout << endl;
}
void heapAdjust(int a[], int low, int high)
{
  int pivotKey = a[low - 1];
  int i;
  for(i = 2 * low; i <= high; i *= 2) 
  {
    if(i < high && a[i - 1] < a[i])
    {
      i++; //i指向較大值
    }
    if(pivotKey >= a[i - 1])
    {
      break;
    }
    a[low - 1] = a[i - 1];
    low = i; 
  }
  a[low - 1] = pivotKey; 
}
void heapSort(int a[], int n)
{
  int i, tmp;
  for(i = n/2; i > 0; i--) 
  {
    heapAdjust(a, i, n);
    print(a, n);
  }
  for(i = n; i > 1; i--)
  {
    tmp = a[i -1];
    a[i - 1] = a[0];
    a[0] = tmp;
    heapAdjust(a, 1, i - 1); 
    print(a, n);
  }
}
int main()
{
  int a[] = {30, 20, 40, 10, 0, 60, 80, 70};
  int n = sizeof(a) / sizeof(a[0]);
  heapSort(a, n);
  print(a, n);
  return 0;
}

最終的排序結果如下：

0 10 20 30 40 60 70 80

堆是一種重要的數據結構，堆排序也是非常重要的算法。在筆試面試中，經常考到堆的相關應用。

我們也會一步一個腳印，爭取每篇文章講清講透一件事，也希望大家閱讀後有所收穫，心情愉快。

你好，我是道哥，CSDN 前 30 名，曾混跡於 BAT 大廠。公衆號講解計算機基礎、網絡、數據結構、算法、C++、Java、Golang 等多方面的編程知識。歡迎點擊如下名片關注道哥，感謝點贊和在看支持哦。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/L2oxHKiQbj5OL2FK9eLe4w

圖解堆排序

堆排序實現

猜你喜歡