Notes of Reading Introduction to Algorithm —— Heapsort

Heaps

A binary heap can be stored in an array.

If we know the index of a node, we can easily work out the indices of its parent, left child and right child. Therefore, we have the three functions to get the indices of them below.

int PARENT(int i)
{
    return i/2;
}
int LEFT(int i)
{
    return 2*i;
}
int RIGHT(int i)
{
    return 2*i+1;
}

Max-heap: For every node other than the root, A[PARENT(i)] >= A[i].

Min-heap: For every node other than the root, A[PARENT(i)] <= A[i].

The following passage will take Max-heap as an example to explain Heapsort.

Maintaining the heap property

When the binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps, how to ensure that the tree rooted at (i) is a max-heap? We can use the function —— MaxHeapify here to maintain the max-heap property.

void MaxHeapify(MaxHeap *A, int i)
{
    int l, r, largest;
    l = LEFT(i);
    r = RIGHT(i);
    if (l <= A->size && A->numbers[l] > A->numbers[i]) {
        largest = l;
    }
    else largest = i;
    if (r <= A->size && A->numbers[r] > A->numbers[largest]) {
        largest = r;
    }
    if (largest != i) {
        int temp;
        temp = A->numbers[i]; A->numbers[i] = A->numbers[largest]; A->numbers[largest] = temp;
        MaxHeapify(A, largest);
    }
}

The running time of the function is $\Theta(1)$Θ(1) to find the largest index among (i), LEFT(i) and RIGHT(i), plus the time to run the function on a subtree (It is based on the assumption that the largest index is not (i).). In the worst case, the time is related to the number of the levels of the tree rooted at (i). Therefore, $T(n) = O(h) = O(\lg n)$T(n)=O(h)=O(lgn).

And then we study the relationship between the numbers of nodes and the numbers of levels:

1. There are all $2^{h-1} - 1$2h−1−1 nodes on the 1 to h-1 levels, and there are at most $2^{h-1}$2h−1 nodes on the h level.
2. With the array representation for storing an n-element heap, the leaves are the nodes indexed by int(n/2)+1, …, n.

Building a heap

As we known before, the leaves are the nodes indexed by int(n/2)+1, …, n. Therefore, the tree (Only a node can be seen as a tree) rooted at nodes indexed by int(n/2)+1, …, n are just max-heaps. What we should do next is to heapify the binary tree from the tree indexed by int(n/2) down to 1.

void BuildMaxHeap(MaxHeap *A)
{
    A->numbers[0] = INFINITY;
    int i = A->size / 2;
    for (; i > 0; i--) {
        MaxHeapify(A, i);
    }
}

As for the h level, there are at most $2^{h-1}$2h−1 nodes, and the time of MaxHeapify is $\Theta(h)$Θ(h). Therefore, the time of BuildMaxHeap equals $\sum\limits_{h=0}^{\lfloor{\lg n}\rfloor }2^{h-1} O(\lfloor{\lg n}\rfloor -h)=O(\sum\limits_{h=0}^{\lfloor{\lg n}\rfloor }(\lfloor{\lg n}\rfloor -h)2^{h-1} )=O(n-\frac{(n+1)\lfloor{\lg n}\rfloor}{2})=O(n)$h=0∑⌊lgn⌋​2h−1O(⌊lgn⌋−h)=O(h=0∑⌊lgn⌋​(⌊lgn⌋−h)2h−1)=O(n−2(n+1)⌊lgn⌋​)=O(n).

Therefore, the tight upper bound is $O(n)$O(n).

Heapsort

We can exchange the root of the Max-heap binary tree with the last node of it, and then turn the new tree to a new Max-heap tree to sort an array.

void Heapsort(MaxHeap *A)
{
    BuildMaxHeap(A);
    for (int i = A->size; i > 1; i--) {
        int temp;
        temp = A->numbers[i];
        A->numbers[i] = A->numbers[1];
        A->numbers[1] = temp;
        A->size--;
        MaxHeapify(A, 1);
    }
}

The time of Heapsort is $O(n\lg n)$O(nlgn), since the BuildMaxHeap takes $O(n)$O(n), and for each elements in the array MaxHeapify takes $O(\lg n)$O(lgn).

The advantage of Heapsort are interpreted in the book Introduction to Algorithm:

Like merge sort, but unlike insertion sort, heapsort’s running time is $O(n\lg n)$O(nlgn). Like insertion sort, but unlike merge sort, heapsort sorts in place: only a constant number of array elements are stored outside the input array at any time.

My complete code are shown below:

#include <iostream>
#include <cstdlib>

#define MaxLength 300
#define INFINITY 65535
#define MaxNum 2000

using namespace std;

struct MaxHeap
{
    int numbers[MaxLength + 1];
    int capacity = MaxLength + 1;
    int size;
};

int PARENT(int i)
{
    return i/2;
}
int LEFT(int i)
{
    return 2*i;
}
int RIGHT(int i)
{
    return 2*i+1;
}

void MaxHeapify(MaxHeap *A, int i)
{
    int l, r, largest;
    l = LEFT(i);
    r = RIGHT(i);
    if (l <= A->size && A->numbers[l] > A->numbers[i]) {
        largest = l;
    }
    else largest = i;
    if (r <= A->size && A->numbers[r] > A->numbers[largest]) {
        largest = r;
    }
    if (largest != i) {
        int temp;
        temp = A->numbers[i]; A->numbers[i] = A->numbers[largest]; A->numbers[largest] = temp;
        MaxHeapify(A, largest);
    }
}

void BuildMaxHeap(MaxHeap *A)
{
    A->numbers[0] = INFINITY;
    int i = A->size / 2;
    for (; i > 0; i--) {
        MaxHeapify(A, i);
    }
}

void Heapsort(MaxHeap *A)
{
    BuildMaxHeap(A);
    for (int i = A->size; i > 1; i--) {
        int temp;
        temp = A->numbers[i];
        A->numbers[i] = A->numbers[1];
        A->numbers[1] = temp;
        A->size--;
        MaxHeapify(A, 1);
    }
}

int main()
{
    MaxHeap *A = new MaxHeap;
    A->size = 0;
    A->capacity = MaxLength + 1;
    for (int i = 1; i < A->capacity; i++) {
        A->numbers[i] = rand() % MaxNum;
        A->size++;
    }
    
    for (int i = 1; i < A->capacity; i++) {
        cout << A->numbers[i] << '\t';
    }
    cout << endl;
    
    Heapsort(A);
    
    for (int i = 1; i < A->capacity; i++) {
        cout << A->numbers[i] << '\t';
    }
}

Reference: Introduction to Algorithm