Heapsort (堆積排序)

Sorting Problem

Input: A sequence of n numbers { $a_0, a_1, ... , a_{n-1}$}

Output: A permutation (reordering) { $a'_0, a'_1, ... , a'_{n-1}$} of the input sequence such that $a'_0 \geq a'_1 \geq ... \geq a'_{n-1}$

Heap Sort 概念

把 array 轉換成 max-heap，這是一種滿足 max-heap property 的 binary tree：對於除了 root 之外的每個 node i, A[parent(i)] $\geq$ A[i]。

重複從 max-heap 取出數值最大的 node (把 root node 和 last node 交換，把交換後的 last node 移出 heap)，並讓殘餘的 heap 維持 max-heap property。

C++ implementation

	#include <iostream>
	#include <vector>
	using namespace std;
	void printArray(vector<int> &vec) {
	for (int i=0; i<vec.size(); i++) {
	cout << vec[i] << " ";
	}
	cout << endl;
	}
	void swap(int &p1, int &p2){
	int temp = p1;
	p1 = p2;
	p2 = temp;
	}
	void maxHeapify(vector<int> &vec, int i, int heap_size) {
	// preconditions: binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps,
	// but node_i might be smaller than its children
	// operation: lets the value at node_i "float down" in the max-heap
	// so that the subtree rooted at index i obeys the max-heap property.
	int l = i * 2 + 1;
	int r = i * 2 + 2;
	int largest = i;
	if ((l < heap_size) && (vec[l] > vec[i]))
	largest = l;
	else
	largest = i;
	if ((r < heap_size) && (vec[r] > vec[largest]))
	largest = r;
	if (largest != i) {
	swap(vec[i], vec[largest]);
	maxHeapify(vec, largest, heap_size);
	}
	}
	void buildMaxHeap(vector<int> &vec, int heap_size) {
	for (int i=(heap_size-1)/2; i>=0; i--) {
	maxHeapify(vec, i, heap_size);
	}
	}
	void heapSort(vector<int> &vec) {
	int heap_size = vec.size();
	buildMaxHeap(vec, heap_size);
	for (int i=vec.size()-1; i>=1 ; i--) {
	// node_0 is the maximum element, swap node_0 with node_heap_end
	swap(vec[0], vec[i]);
	// now node_heap_end is the maximum element
	// extract node_heap_end by reducing heap size by one
	heap_size--;
	// make node 0 the maximum element
	maxHeapify(vec, 0, heap_size);
	}
	}
	int main(int argc, char** argv) {
	int array1[] = {38, 27, 43, 3, 9, 82, 10};
	vector<int> vec1(array1, array1+sizeof(array1)/sizeof(array1[0]));
	cout << "original array:" << endl;
	printArray(vec1);
	heapSort(vec1);
	cout << "sorted array:" << endl;
	printArray(vec1);
	return 0;
	}

view raw Heapsort.cpp hosted with ❤ by GitHub

Performance Analysis

Worst case performance: $O(n \log n)$

Space complexity: $O(1)$ auxiliary

延伸閱讀

[書籍] Introduction to Algorithms, 3rd. edition - Chap 6 Heapsort

[WiKi] 堆積排序

[WiKi] Heapsort

[WiKi] Heap (data structure)

系列文章

Insertion Sort (插入排序)

Merge Sort (合併排序)

Heapsort (堆積排序)