heapsort — using a priority queue implemented as a heap

using a priority queue ADT

void HeapSort(Item a[], int lo, int hi) {
	// insert all items into priority queue (heap)
	PQ pq = PQNew();
	for (int i = lo; i <= hi; i++) {
		PQJoin(pq, a[i]);
	}

	// extract all items from priority queue (heap)
	for (int i = lo; i <= hi; i++) {
		Item it = PQLeave(pq);
		a[i] = it;
	}

perfomance analysis

time complexity: O(n log n)

each insert into a heap is O(log n)

there must be $n$ insertions

space complexity: O(n)

since we must insert $n$ items into the priority queue

<aside> ❗ but this approach is quite bad memory-wise… is it possible to do an in-place sort?

</aside>

force an item into the correct position in a heap: fixDown()

the fixDown() functions forces an item at index i into the current position in the heap

psuedo-code for a max-heap:

void fixDown(Item a[], int i, int N) {
	while (2 * i <= N) {
		int child = 2 * i;
		
		// figure out if left_child or right_child is greater
		if (child < N && a[child] < a[child + 1]) child++;

		// if curr is greater than greater child, then dont swap
		if (a[i] >= a[child]) break; 

		// otherwise, swap curr item with child
		swap(a, i, child);

		// move down one level in the heap
		i = child;
	}
}

fixDown is an O(log n) function

in-place heapsort

void HeapSort(Item a[], int lo, int hi) {
	int i, N = hi - lo + 1;
	Item *h = a + lo - 1; // allows us to treat index 1 as start of array
	// h is a pointer to the block of memory 1 before the heap

	for (i = N/2; i > 0; i--) fixDown(h, i, N);
	
	// ! at this point, the array has been converted into a max heap ! //

	while (N > 1) {
		// move largest value at the end of the array
		swap(h, 1, N);
		// reduce heap size by 1
		N--;
		// restore heap property after swap
		fixDown(h, 1, N);
	}
}