① 【跟著小蛋刷演算法】什麼是堆如何實現堆排序，滿滿的干貨來了
堆可以理解為特殊樹形結構，滿足兩個條件：完全二叉樹與值的比較規則（大頂堆或小頂堆）。完全二叉樹特點是除最後一層外，其他層節點滿載，最後一層靠左排列。大頂堆為每個節點大於或等於子節點，小頂堆為每個節點小於或等於子節點。以下圖示為堆的示例。
構建堆採用數組形式。每個節點存儲在數組的第二位置開始，定義節點在數組的位置為i，左子節點為2i，右子節點為2i+1。通過此規律可以推導出節點關系。接下來通過代碼實現堆的各種功能。
往堆中插入元素時，需滿足堆的特性。如果插入後不滿足，執行堆化操作，即新插入的節點與父節點比較，若不滿足子節點小於等於父節點則交換節點值，重復過程直到堆滿足特性。此過程如圖示。
刪除堆頂元素，即刪除堆中最大元素。將堆頂元素值與最後一個節點值互換，再執行堆化過程，直到堆滿足特性。圖示此過程。
堆排序利用堆進行排序。首先將序列構造成大頂堆，最大值在堆頂。接著交換堆頂元素與末尾元素，將剩餘元素重新構造成堆，得到次大值，反復執行得到有序序列。
實現堆排序的第一步是構建大頂堆，採用從上往下的堆化方式。假設待排序序列{0,7,5,19,8,4,1,20,13,16}，堆元素從數組下標1開始，總共有9個元素。循環從9/2=4開始，直至1，因為這些節點有子節點。
排序過程是不斷將堆頂元素與末尾元素交換，將堆元素減1，然後重新堆化，重復直至完成排序。整個過程如圖所示。
堆排序時間復雜度包括構建堆與排序，構建堆為O(n)，排序為O(nlogn)，整體時間復雜度為O(nlogn)。
堆的概念、插入與刪除操作、堆排序與排序代碼詳解。總結堆知識點，堆排序流程，以及建堆和排序的代碼實現。
堆的知識點已大致講解，但演算法之路漫長，繼續堅持學習。關注小蛋，一起交流進步，更多的演算法干貨將不斷推出。