《算法導論》代碼搬運工--堆排序

最近買了本中文版的《算法導論》，打算系統的看一下基礎的算法，并盡量的實作一下書上的代碼例子。書很厚，内容很多，有簡單的也有難懂的，是以打算開一個新的系列，長期不定時的加入新的内容，就叫《算法導論》代碼搬運工系列。代碼基本都是用java實作的，實作語言并不重要，java和C的文法差别也并不大。

這一篇來搬運一個基礎的排序算法：堆排序。

堆排序：顧名思義，就是用堆來實作排序的功能，那麼在堆排序之前就先要知道什麼是堆，怎麼建堆。

《算法導論》中用數組來表示一個堆（二叉堆），如下圖，那麼堆中元素和元素之間的關系就需要使用數組下标來維護了，對一個二叉堆，用層序來依次存儲到一維數組中，那麼對于一個下标為 i 的元素a[i]，它的parent(i)節點可以表示為a[i/2]，當然i/2是取floor，左孩子left(i)可以表示為a[i*2]，右孩子right(i)可以表示為a[i*2+1]（注意下标不越界）。其他堆的性質就很簡單了，例如最大堆，那麼父親節點的值一定是大于等于兩個孩子節點的值的。

對于堆排序，有三種基本的操作：max-heapify, build-max-heap, heapsort，依次是最大化一個堆（隻能針對目前堆，對于目前堆影響不到的其他子堆，算是一次原子操作--我自己的了解），建立一個完整的最大堆（對于一個堆的很多次max-heapify操作，使得整個堆成為最大/最小堆），以及最後的利用堆來排序。

下面是三種操作的java代碼：

max-heapify：

public void max_heapify(int a[], int index, int heap_size) {
		int left_index = index * 2;
		int right_index = index * 2 + 1;
		int largest = index;
		if (left_index < heap_size && a[left_index] > a[index])
			largest = left_index;
		if (right_index < heap_size && a[right_index] > a[largest])
			largest = right_index;
		if (largest != index) {
			int temp = a[index];
			a[index] = a[largest];
			a[largest] = temp;
			max_heapify(a, largest, heap_size);
		}
	}
           

過程就是，找出目前節點和它左右孩子中最大的那個，如果最大的不是自己，那麼和自己交換，并且對被交換那個下标遞歸執行目前步驟（之前有過一個困惑，我以為應該對下标為index的做遞歸，其實要注意到這裡的largest下标是固定的，而其中的元素被改變了，是以針對的遞歸對象應該是以下标為準）。

build-max-heap：

int a[] = { Integer.MIN_VALUE, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
		Heap_sort hs = new Heap_sort();
		int heap_size = a.length;
		// 因為下标n/2+1後面的元素都是葉節點，是以隻要從非葉節點開始往下周遊就可以，葉子節點沒有必要周遊
		for (int i = heap_size / 2; i >= 1; i--) {
			hs.max_heapify(a, i, a.length);
		}
           

因為0下标需要額外判斷，不如讓有效内容從下标1開始，然後對非葉子節點進行周遊執行max-heapify操作，因為葉子節點沒有孩子，是以沒有必要去周遊，又由于二叉堆是完全二叉樹，是以下标n/2後面的節點都是葉子節點。

heapsort：

public void heap_sort(int a[]) {
		int heap_size = a.length;
		for (int i = a.length - 1; i > 1; i--) {
			int temp = a[i];
			a[i] = a[1];
			a[1] = temp;
			heap_size--;
			max_heapify(a, 1, heap_size);
		}
	}
           

注意到前面的max-heapify有一個參數是heap_size，如果不牽涉到排序，那麼這個參數就一直是數組的length，但是如果牽涉到排序，這個有效length是會變的。因為堆排序的過程是這樣的：根據大頂堆的性質，堆頂元素，也就是根節點的值一定是最大的，是以每一次都把堆頂元素和最後一個葉子節點交換，再把這個堆頂元素從堆裡面踢出去放在這個數組的末尾，然後把原來的堆最大化，那麼下一個最大的元素又冒出來了，再做一樣的動作直到堆中元素都被按照順序排列到數組中，這個數組就是這一堆數字的升序排列（降序隻需要做一個小頂堆即可）。

再提一下每一個排序算法都很關注的時間複雜度，堆排序的時間複雜度是O(nlgn)，因為并不需要額外的空間，是以空間複雜度一直都是常數級，是原址排序（就地排序）。

在練習題中，有兩道證明題，一個是證明在最壞情況下，堆排序的時間複雜度是Ω(nlgn)，另一個是證明在所有元素都不同的情況下，堆排序的時間複雜度是Ω(nlgn)，不去深究如何證明，但是可以知道堆排序的時間複雜度的數量級一直是nlgn的。對于O, Ω和Θ的定義可以去翻一下數學書，對于一個算法的時間複雜度的界的定義，但是不去特别深究也問題不大。