showing the difference between williams and floyds heapsort implementations.

heapsort.cpp

#include <iostream>
using namespace std;

template <class T>
void print(T a[], int n) {
    for (int i = 0; i < n; i++) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

template <class T>
void exch(T a[], int l, int r) {
    T t = a[l]; a[l] = a[r]; a[r] = t;
}

template <class T>
void siftdown(T a[], int n, int k) {
    int j;
    T v = a[k];
    while (k <= n/2) {
        j = k+k;
        if (j < n && a[j] < a[j+1]) j++;
        if (v >= a[j]) break;
        a[k] = a [j];
        k = j;
    }
    a[k] = v;
}

template <class T>
void siftup(T a[], int n, int k) {
    T v = a[k];
    while (k > 0 && a[k/2] <= v) {
        a[k] = a[k/2];
        k = k/2;
    }
   a[k] = v;
}

//worst cases comparisons are O(nlogn), but this version
//is slower because the heapify it uses is O(nlogn)
//this is Williams original version
template <class T>
void heapsortTD(T a[], int l, int r) {
    int n = r-l;
    T *pq  = a+l;
    for (int i = 1; i < n-1; i++)
        siftup(pq, n, i);
    print(pq, n);
    while (n > 0) {
        exch(pq, 0, n--);
        siftdown(pq, n, 0);
    }
}

//worst case comparisons is O(nlogn) but this version is
//faster because bottom up heapify is done in O(n)
//this is Floyds Tree-Sort
template <class T>
void heapsortBU(T a[], int l, int r) {
    int n = r-l;
    T *pq = a+l;
    //phase 1
    for (int i = n/2; i >= 0; i--)
        siftdown(pq, n, i);
    print(pq, n);
    //phase 2
    while (n > 0) {
        exch(pq, 0, n--);
        siftdown(pq, n, 0);
    }
}


int main() {
    int n = 15;
    int *a = new int[n];
    int *b = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 100;
        b[i] = a[i];
    }
    print (a, n);
    cout<<"Heaps: "<<endl;
    cout<<"Top Down:  ";
    heapsortTD(a, 0, n-1);
    cout<<"Bottom up: ";
    heapsortBU(b, 0, n-1);
    cout<<"Results: "<<endl;
    cout<<"Top Down:  ";
    print(a, n);
    cout<<"Bottom up: ";
    print(b, n);
}