《算法導論》@讀書筆記@ 第六章 - 堆排序(包含js版代碼實作)

什麼是堆排序

堆（英語：heap)是計算機科學中一類特殊的資料結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：

• 堆中某個節點的值總是不大于或不小于其父節點的值；
• 堆總是一棵完全二叉樹。

在javascript中我們用數組來實作這一種資料結構

堆排序就是利用這種資料結構進行排序

算法思路

就是建立一個最大堆,然後利用堆頂永遠是最大數值來排序

如下圖所示,每次都将黃色區域的值(堆頂)與粉紅區域的值(末位)進行交換

然後排除末位 在剩下的數組中進行最大堆重塑

如此往複,到這個堆隻剩下一個元素 就完成了整個排序過程

算法過程

1. 首先定義一個排序方法

   HeapSort

2. 然後我們需要建立一個最大堆

   BuildMaxHeap

3. 然後我們需要一個維護堆的性質的方法,也就是重塑堆得方法

   MaxHeap

4. 往複的從堆頂與數組末位互換位置 然後重塑

BuildMaxHeap

的前提是我們要先把數組看成一個堆,看成堆了之後我們要知道數組中的位置和堆的位置的對照關系,如下圖所示

我們以堆底開始利用

MaxHeap

建構最大堆

MaxHeap

是假設存在一個堆,它的堆頂的左節點和右節點都是符合最大堆的性質的

算法實作

/**
 * 時間複雜度 平均：O(nlog2n)。
 * 空間複雜度：O(1)。
 * 穩定性：不穩定
 */

function HeapSort(arr) {
	var len = arr.length;
	BuildMaxHeap(arr,len);
	for (var i = len-1 ; i > 0; i--) {
		let box = arr[0];
		arr[0] = arr[i];
		arr[i] = box;
		MaxHeap(arr,0,i);
	}
	return arr
}

function MaxHeap(arr,i,length) {
	var largest = null;
	var node = arr[i]; //儲存目前節點
	var left = i * 2 + 1 ; //定位節點左
	var right = i * 2 + 2; //定位節點右	
	//判斷目前有這個節點 （這裡會存在目前這個的子節點不存在的情況）處理一下邊界情況
	if (left < length && node < arr[left]) {
		largest = left
	}else{
		largest = i;
	}
	if (right < length && arr[largest] < arr[right]) {
		largest = right
	}
	//如果不是i是最大節點 以node作為輔助節點 交換位置
	if (largest != i) {
		arr[i] = arr[largest];
		arr[largest] = node;
		MaxHeap(arr,largest,length);
	}
}
//建立一個最大堆
function BuildMaxHeap(arr,len){
	if(len%2!=0){
		len = len +1 ;
	}
	for(let i = len/2;i>=0;i--){
		MaxHeap(arr,i,len)
	}
}