heapsort — using a priority queue implemented as a heap
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;
}
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>
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
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);
}
}