堆積排序Heapsort

說明 · Heapify：將陣列轉換為heap 資料結構（heapify）。

· Sorting：不斷置換heap root 與最後一個元素來排序，並修正剩餘未排序資料使其符合heap order。

RustAlgorithmClub💡基礎概念漸進符號AsymptoticNotation🔍搜尋線性搜尋Linearsearch二元搜尋Binarysearch內插搜尋Interpolationsearch指數搜尋Exponentialsearch📚排序簡單排序插入排序Insertionsort選擇排序Selectionsort氣泡排序Bubblesort希爾排序Shellsort高效排序堆積排序Heapsort快速排序Quicksort合併排序Mergesort混合排序🚧內省排序Introsort🚧自適應合併排序Timsort🚧模式消除快速排序Pdqsort特殊排序計數排序Countingsort桶排序Bucketsort基數排序Radixsort🏠資料結構堆疊與佇列堆疊Stack佇列Queue雙端佇列Deque鏈結串列鏈結串列概述單向鏈結串列Singlylinkedlist🚧雙向鏈結串列Doublylinkedlist🚧循環鏈結串列Circularlinkedlist關聯容器關聯容器概述雜湊表Hashmap🚧有序映射表Orderedmap🚧多重映射表Multimap集合Set布隆過濾器Bloomfilter🧵字串處理漢明距離Hammingdistance萊文斯坦距離Levenshteindistance🚧最長共同子字串Longestcommonsubstring貢獻指南404 Light(default) Rust Coal Navy Ayu RustAlgorithmClub Heapsort（堆積排序）可以看作是selectionsort的變形，同樣會將資料分為sortedpile與unsortedpile，並在unsortedpile中尋找最大值（或最小值），加入sortedpile中。

和selectionsort不同之處是，heapsort利用堆積（heap）這種半排序（partiallysorted）的資料結構輔助並加速排序。

Heapsort的特性如下： 使用heap資料結構輔助，通常使用binaryheap。

不穩定排序：排序後，相同鍵值的元素相對位置可能改變。

原地排序：不需額外花費儲存空間來排序。

較差的CPU快取：heap不連續存取位址的特性，不利於CPU快取。

Heapsort的演算法分為兩大步驟： 將資料轉換為heap資料結構（遞增排序用max-heap,遞減排序選擇min-heap）。

逐步取出最大／最小值，並與最後一個元素置換。

具體步驟如下： 交換heap的root與最後一個node，縮小heap的範圍（排序一筆資料，故heap長度-1）。

更新剩下的資料，使其滿足heap的特性，稱為heaporderingproperty。

重複前兩個步驟，直到heap中剩最後一個未排序的資料。

透過GIF動畫感受一下heapsort的威力吧！ 在開始之前，定義幾個heap常用名詞： Heaporderingproperty：一個heap必須要滿足的條件。

以heap種類不同有幾種變形。

min-heapproperty：每個結點皆大於等於其父節點的值，且最小值在heaproot。

max-heapproperty：每個結點皆小於等於其父節點的值，且最大值在heaproot。

而heapsort主要分為兩個部分： Heapify：將陣列轉換為heap資料結構（heapify）。

Sorting：不斷置換heaproot與最後一個元素來排序，並修正剩餘未排序資料使其符合heaporder。

這裡有一個未排序的序列，將以遞增方向排序之。

[17,20,2,1,3,21] 首先，將資料轉換為heap資料結構，這個步驟即時heapify。

由於是遞增排序，我們採用max-heap（最大元素在root）。

[21,20,17,1,3,2] 對應的二元樹（binarytree）的圖形如下： 再來就是排序的部分，Max-heap會將最大的元素擺在root的位置，我們先將最後一個node與root進行交換，完成第一個排序步驟。

若不熟悉heap，可以閱讀Wiki的介紹，其實heap就是用陣列實作的二元樹。

[21,20,17,1,3,2] ** (swap)--> unsorted|sorted [2,20,17,1,3|21] 接下來，將未排序的資料區塊重整為符合max-heap的結構。

[2,20,17,1,3|21] (siftdown)--> [20,3,17,1,2|21] 有沒有看出一些端倪？ 只要不斷將root和最後一個node交換，並將剩餘資料修正至滿足heapordering，就完成排序了。

[20,3,17,1,2|21] ** (swap)--> [2,3,17,1|20,21] (siftdown)--> [17,3,2,1|20,21] ** (swap)--> [1,3,2|17,20,21] (siftdown)--> [3,1,2|17,20,21] ** (swap)--> [1,2|3,17,20,21] (Done!) 以上便是heapsort演算法的簡單流程，是不是和selectionsort非常相似呢！ Complexity Worst$O(n\logn)$ Best$O(n\logn)$ Average$O(n\logn)$ Worstspace$O(1)$auxiliary Heapsort最佳、最差、平均的時間複雜度皆為$O(n\logn)$，同樣分為兩部分簡單解釋。

建立一個binaryheap有兩種方法，一種是一個個元素慢慢加入heap來建立；另一種則是給定隨意的序列，再透過heapify演算法修正序列為有效的heap。

一般來說heapsort常用實作後者。

Heapify是指將序列修正至符合heapordering的序列。

給定一個元素，假定其為非法的heaporder，而該元素之後的subtree視為符合heaporderingproperty。

欲修正這個在錯誤位置的元素，必須透過與其childrennode置換往下篩，這個往下篩的過程就稱為siftdown，在實作一節會詳細解釋，這邊只要知道siftdown會不斷將該元素與其childnode比較，若不符合heaporder則與childnode置換，並繼續疊代每一個level。

所以siftdown的時間複雜度為$O(\lceil{\log_2(n)}\rceil)=O(\logn)$，$n$為陣列元素個數。

Heapify從最末個元素開始反向疊代，每個元素都呼叫sift_down調整heap符合heapordering。

總共要做$n$次sift_down操作，但由於最後一層所以leaf已符合heaporder（因為沒有childnode），我們的迴圈可以跳過所有leafnode直接從非leafnode開始，因此複雜度為 $$\lfloorn/2\rfloor\cdotO(\logn)=O(n\logn)$$ 實際上，buildheap步驟的複雜度可達到$O(n)$，可以看看UMD演算法課程Lecturenote的分析。

講完了heapify，就換到排序部分，所謂的排序其實就是利用max-heap（或min-heap）的最大值（最小值）會在首個元素的特性，與最後一個元素置換，完成排序，並將剩餘的部分透過siftdown修正符合heaporder。

所以總共需要做$n$次siftdown，複雜度為$O(n\logn)$。

綜合這兩部分，可以看出Sortingpart對複雜度有決定性影響，最佳複雜度為$O(n\logn)$。

Heapsort的實作相對簡單，只需要不斷呼叫heap內部的sift_down方法就可以完成排序。

整個演算法架構如下： #![allow(unused)] fnmain(){ pubfnheapsort(arr:&mut[i32]){ //--Heapifypart-- //Thisprocedurewouldbuildavalidmax-heap. //(ormin-heapforsortingdescendantly) letend=arr.len(); forstartin(0..end/2).rev(){//1 sift_down(arr,start,end-1); } //--Sortingpart-- //Iterativelysiftdownunsortedpart(theheap). forendin(1..arr.len()).rev(){//2 arr.swap(end,0);//3 sift_down(arr,0,end-1);//4 } } } 這部分是heapify，從最小non-leafnode開始（end/2），修正序列至滿足heaporder，再反向疊代做heapify。

這部分負責排序，每次疊代都將排序heap的root元素，步驟如3-4： 不斷將max-heap中最大值（在root上）與heap最後一個元素end置換， 並利用sift_down將序列修正至max-heap資料結構，依照定義，此時unsortedpile首個元素成為max-heaproot，是最大值。

Heapsort全靠sift_down神救援，那sift_down到底有什麼神奇魔力，一探究竟吧！ #![allow(unused)] fnmain(){ fnsift_down(arr:&mut[i32],start:usize,end:usize){ letmutroot=start; loop{ letmutchild=root*2+1;//Gettheleftchild//1 ifchild>end{ break; } ifchild+1<=end&&arr[child]