文章出處：極客時間《數據結構和算法之美》-作者：王爭。該系列文章是本人的學習筆記。

1 堆定義

1.1 定義和結構

堆是一個完全二叉樹（完全二叉樹：除了葉子節點外每一層節點都是滿的，最后一層的子節點都靠左排列）；堆中每個節點的值都大于等于（或小于等于）其子樹中的每個節點的值。
　　因為堆是一個完全二叉樹，所以可以用數組來表示堆。如果根節點存在在下標為1的位置。下標i存儲節點，下標2i存儲節點的左子節點，2i+1存儲節點的右子節點。

1.2 操作和存儲結構

1.2.1 插入元素

　　向一個堆中插入一個元素，直接放在最后一個位置可能會破壞堆的結構，于是就需要進行調整。這個過程稱為堆化。堆化分為兩種：從下向上、從上往下。現在先看從下向上。堆化就是沿著路徑不斷向上比較，如果不滿足大小關系，就交換。直到滿足堆條件。
　　

1.2.2 刪除堆頂元素

當刪除堆頂的元素之后，需要做一些操作才能稱為新的堆。假設刪除的是一個大頂堆，堆頂放的是最大元素。

　　刪除堆頂元素33，將最后一個節點的值12賦值給根節點。然后對根節點做堆化，從上往下的。如果不滿足大小關系，將根節點沿著路徑選擇較大值的子節點和根節點交換。繼續交換直到滿足堆定義。

1.3 相關代碼

代碼

2 堆排序

堆排序時間復雜度是O(nlogn)，是原地排序，但不是穩定排序。堆排序過程分為建堆和排序兩個階段。

2.1建堆

輸入一個數組，原地將這個數組建堆，不使用額外的空間。
我們可以把這個過程看作是堆的插入過程。先假設堆起初只包含下標為1的元素。調用插入方法將下標從2到n的數據依次插入。這樣建堆就完成了。
第二種處理方法是從后往前處理數據。對每一個數據做從上往下的堆化。也就是說以當前節點為根節點，比較其與子樹上每個節點的值，保證符合堆定義。葉子節點堆化只能和自己比較，故，省略，從$\frac{2}{n}$開始處理數據。
如果我們需要從小到大排序數組。在建堆的時候我們可以建一個大頂堆。

2.2 排序

建堆結束，我們已經有了一個大頂堆。堆頂元素是最大的。如果我們把堆頂元素和最后一個元素交換位置，模擬堆頂元素刪除操作，將這n-1個元素堆化。繼續將堆頂元素和倒數第二個元素交換位置，繼續堆化這n-2個元素。直至堆的大小為1，則得到一個從小到大排序的數組。

2.3 時間復雜度

1 用遞歸樹法求建堆的時間復雜度：O(n)。
2 排序時間復雜度：O(nlogn)。
所以最終時間復雜度O(nlogn)。

2.4 為什么使用快排而不是堆排序

1 因為堆排序的比較次數、移動次數比較高。
2 堆排序不是穩定排序。在前后交換過程中會改變數據的前后順序。
3 數據訪問方式是跳躍式的，不利于使用CPU緩存機制。

代碼

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的数据结构六——堆的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。