1 引言?
什么是堆？
堆是一種滿足以下條件的樹：（樹這一篇可以參考我的文章數據結構秘籍（三）樹 （含二叉樹的分類、存儲和定義）-CSDN博客）
堆中的每一個結點值都大于等于（或小于等于）子樹中所有結點的值。
很多博客說堆是完全二叉樹，其實并非如此，堆不一定是完全二叉樹，只是為了方便存儲和索引，我們通常用完全二叉樹的形式來表示堆，事實上，廣為人知的斐波那契堆和二項堆就不是完全二叉樹,它們甚至都不是二叉樹。
? （二叉）堆是一個數組，它可以被看成是一個 近似的完全二叉樹。——《算法導論》第三版
判斷一下下面給出的圖是否是堆
?第1 個和第 2 個是堆。第 1 個是最大堆，每個節點都比子樹中所有節點大。第 2 個是最小堆，每個節點都比子樹中所有節點小。第3個不是，在第三個中，有的結點比子結點小，有的比子結點大不符合堆的特性。
2 堆的用途
當我們只關心所有數據中的最大值或者最小值，存在多次獲取最大值或者最小值，多次插入或刪除數據時，就可以使用堆。
對比有序數組而言，初始化一個有序數組時間復雜度是 O(nlog(n))，查找最大值或者最小值時間復雜度都是 O(1)，但是，涉及到更新（插入或刪除）數據時，時間復雜度為 O(n)，即使是使用復雜度為 O(log(n)) 的二分法找到要插入或者刪除的數據，在移動數據時也需要 O(n) 的時間復雜度。
相對于有序數組而言，堆的主要優勢在于插入和刪除數據效率較高。 因為堆是基于完全二叉樹實現的，所以在插入和刪除數據時，只需要在二叉樹中上下移動節點，時間復雜度為O(log(n))，相比有序數組的 O(n)，效率更高。
不過，需要注意的是：Heap 初始化的時間復雜度為 O(n)，而非O(nlogn)。
3 堆的分類
堆分為最大堆和最小堆。二者的區別在于結點的排序方式。
- 最大堆：堆中的每一個結點的值都大于等于子樹中所有結點的值。
- 最小堆：堆中的每一個結點的值都小于等于子樹中所有結點的值。
在下圖中，圖1是最大堆，圖2是最小堆。
4 堆的存儲
之前介紹樹的時候說過，由于完全二叉樹的優秀性質，利用數組存儲二叉樹即節省空間，又方便索引（若根結點的序號為 1，那么對于樹中任意節點 i，其左子節點序號為 2*i，右子節點序號為 2*i+1）。
為了方便存儲和索引，（二叉）堆可以用完全二叉樹的形式進行存儲。存儲的方式如下圖所示：
5 堆的操作
堆的更新操作主要包括兩種：插入元素和刪除堆頂元素。操作過程需要著重掌握和理解。
5.1 插入元素
在堆內進行插入的時候，我們會將插入的元素放到最后
5.1.1 將要插入的元素放到最后
5.1.2 從底向上，如果父結點比該元素小，則該結點和父結點交換 ，直到無法交換
?
5.2 刪除堆頂元素（這里拿最大堆舉例）
?根據堆的性質可以知道，最大堆的堆頂元素為所有元素中最大的，最小堆的堆頂元素是所有元素中最小的。當我們需要多次查找最大元素或者最小元素的時候，可以利用堆來實現。
刪除堆頂元素后，為了保持堆的性質，需要對堆的結構進行調整，我們將這個過程稱之為“堆化”，堆化的方法分為兩種：
- 一種是自底向上的堆化，上述的插入元素所使用的就是自頂向上的堆化，元素是從最底部向上移動。
- 另一種是自頂向下堆化，元素由最頂部向下移動。
5.2.1 自底向上堆化
打個比方，如果一個公司里出現了boss離職的情況，該怎么辦，看下文
首先刪除堆頂元素，使得數組中下標為1的位置空出。
那誰來頂替這個位置，必須是數足夠大。所以我們比較根結點的左子結點和右子結點，也就是下標為2,3的數組元素，將較大的元素填充到根結點的位置。
這時候，空出來的位置，就依次往下遞歸，誰有能力誰就上。也就是說，一直循環比較空出位置的左右子結點，并將大者移至空位，直到遍歷到堆的最底部。
?
我們可以看到，這個時候已經完成了自底向上的堆化，沒有元素可以填補空缺了，但是，我們可以看到數組中出現了空白，這將會導致存儲空間的浪費。
5.2.2 自頂向下堆化?
自頂向下堆化，有一個特殊的點就是我們需要將堆的最后一個元素從末尾的位置提到堆頂（根結點）上來，再進行堆化。
?
我們不斷的將這個（原來的）?末尾元素，不斷地與左右子結點的值進行比較，和較大的子結點交換位置，直到無法交換為止
可能有的小伙伴要問了，這兩個也沒有什么太大的區別啊，重點就在自頂向下堆化不會產生氣泡。
5.3 總結堆的操作
- 插入元素：先將元素放置到元素末尾，再自底向上堆化，使末尾元素上浮。
- 刪除堆頂元素：將末尾元素放置堆頂，再自頂向下堆化，將堆頂元素下沉。也可以自底向上堆化，只是會產生空缺，浪費存儲空間。最好采用自頂向下的堆化方式。
6 堆排序
堆排序的過程分為兩步：
- 第一步是建堆，將一個無序的數組建立為一個堆。
- 第二步是排序，將堆頂元素取出，然后對剩下的元素進行堆化，反復迭代，直到所有的元素被取出為止。
6.1 建堆
建堆的過程就是一個對所有非葉子結點的自頂向下堆化過程。
什么是非葉子結點，就是最后一個結點的父結點及它之前的元素，都是非葉子結點（具體可以了解另外一篇關于樹的相關內容，這里不詳談）。數據結構秘籍（三）樹 （含二叉樹的分類、存儲和定義）-CSDN博客文章瀏覽閱讀689次，點贊27次，收藏22次。根結點的序號為1，對于每個結點Node，假設它存儲在數組中下標為i的位置，那么它的左子結點就存儲在2i的位置，它的右子結點就存儲在下標為2i+1的位置。二叉樹的第i層最多擁有2的（n-1）次方個結點，深度為k的二叉樹至多有2^(k+1)-1個結點（滿二叉樹），至少有2的n次方個結點，這里面的k為深度。二叉樹的先序遍歷是先輸出根結點，再遍歷左子樹，最后遍歷右子樹，遍歷右子樹和左子樹的時候同樣 遵循先序遍歷的規則，也就是說，我們可以遞歸實現先序遍歷。并且，二叉樹的分支具有左右次序，不能隨意顛倒。https://blog.csdn.net/rc1596919047/article/details/145934474?spm=1001.2014.3001.5501也就是說，如果結點個數為n，那么我們需要對n/2到1的結點進行自頂向下堆化。
將初始的無序數組抽象為一棵樹，圖中的結點個數為6個，所以4，5，6結點為葉子結點，1,2,3結點為非葉子結點，所以要對1-3號結點進行自頂向下堆化，注意順序是從后往前堆化，從3號結點開始，一直到1號結點。（為什么是結點3，n為6，非葉子結點就是3-1）。
例如這張圖，非葉子結點就是從5開始到1。（畫的比較抽象，不喜勿噴）
回去看，3號結點堆化結果：
?2號結點堆化結果：
1號結點堆化結果：
?
至此，數組所對應的樹已經成為了一個最大堆，建堆完成。
額外注意的是，堆化是一個完整的過程，而非一個步驟。
6.2 排序
由于堆頂元素是所有元素中最大的，所以我們重復取出堆頂元素，將這個最大的堆頂元素放置數組末尾，并對剩下的元素進行堆化即可。
現在思考兩個問題：
- 刪除堆頂元素后需要執行自頂向下堆化，還是自底向上堆化？
- 取出的堆頂元素存在哪，新建一個數組存嗎？
先回答第一個問題，我們需要執行自頂向下堆化，這個堆化一開始要將末尾元素移動至堆頂，這個時候末尾的位置就空出來了，由于堆中的元素已經減小，這個位置不會再被使用，所以我們可以將取出的元素放在末尾。這其實就是做了一次交換操作，將堆頂和末尾的元素調換位置，從而將取出堆頂元素和堆化的第一步（將末尾元素放置根結點）進行合并。
取出第一個元素并堆化：
取出第二個元素并堆化：
取出第三個元素并堆化：
?
取出第四個元素并堆化：
?
取出第五個元素并堆化：
?
取出第六個元素并堆化：
堆排序就此完成。?
如果覺得我的講解有不足之處，可以在評論區發表意見，我會及時采納改正。更細致的，可以去看一看這篇文章：
數據結構堆(Heap)詳解-堆的建立、插入、刪除、最大堆、最小堆、堆排序等_最大堆 heap 是一個什么樣的存在?-CSDN博客文章瀏覽閱讀7.9w次，點贊153次，收藏447次。基本概念：1、完全二叉樹：若二叉樹的深度為h，則除第h層外，其他層的結點全部達到最大值，且第h層的所有結點都集中在左子樹。2、滿二叉樹：滿二叉樹是一種特殊的的完全二叉樹，所有層的結點都是最大值。什么是堆？堆（英語：heap)是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：堆中某個節點的值總是不大于或不小于其父節點的值；..._最大堆 heap 是一個什么樣的存在?https://blog.csdn.net/xiaomucgwlmx/article/details/103522410
 __declspec(deprecated(msg)))
