Heapsort implementation in C++.

heapsort.h

#ifndef HEAPSORT_H
#define HEAPSORT_H

#include <iostream>
#include <cstddef>
#include <assert.h>
#include <math.h>


using namespace std;


// defines for a 0-based array representation of a complete binary tree
#define PARENT(index)       (floor((index) - 1) / 2)
#define LEFT(index)         (2 * (index) + 1)
#define RIGHT(index)        (2 * (index) + 2)


template<typename T>
inline void xchg(T *array, int a, int b)
{
    T tmp = array[a];
    array[a] = array[b];
    array[b] = tmp;
}


/**
 * Given an array and start and end indices for a subset of that array,
 * think of it as a subtree of a complete binary tree rooted at `array[start]`,
 * and swim the last child node at array[end] to maintain heap order.
 */
template<typename T>
static void swim(T *array, int start, int end)
{
    int node = end;
    while (PARENT(node) >= 0)
    {
        int parent = PARENT(node);

        // if this node's key is bigger than its parent's, swap it
        if (array[node] > array[parent])
        {
            xchg(array, node, parent);
            node = parent;              // go up the tree and repeat
        }
        else
        {
            return;                     // otherwise, this node is at its correct heap order
        }
    }
}


/**
 * Given an array and start and end indices for a subset of that array,
 * think of it as a subtree of a complete binary tree rooted at `array[start]`,
 * and sink that root node to maintain heap order.
 */
template<typename T>
static void sink(T *array, int start, int end)
{
    int root = start;
    while (LEFT(root) <= end)       // while the root has at least one child
    {
        int child = LEFT(root);
        int swap = root;

        // if the root's key is smaller than its child's, potentially swap it
        if (array[swap] < array[child])
        {
            swap = child;
        }
        // if it has a right child, and that right child is also bigger, swap with that one instead
        if ((child + 1) <= end && array[swap] < array[child + 1])
        {
            swap = child + 1;
        }

        if (swap != root)
        {
            xchg(array, root, swap);
            root = swap;            // continue sink down the child we just swapped with
        }
        else
        {
            return;
        }
    }
}


/**
 * Given a complete binary tree represented as an array, heapify it in-place.
 */
template<typename T>
void heapify(T *array, int length)
{
#ifdef TOPDOWN
    // "top-down" implementation: start from the root, swim its children,
    // then repeat going down the tree
    for (int end = 1;                       // start with a subtree root + left child
            end < length;
            end++)                          // expand the subtree at each iteration, working downward
    {
        // maintain heap order for this subtree by "swimming" up the last child node considered
        swim(array, 0, end);
    }
#else
    // "bottom-up" implementation: start from the smallest subtree on the bottom, sink its root,
    // then repeat going up the tree
    for (int start = PARENT(length - 1);   // start with the index of the last parent node
            start >= 0;
            start--)                       // and iterate to the next parent node backwards
    {
        // maintain heap order for the subtree rooted at 'start'
        sink(array, start, length - 1);
    }
#endif
}

template<typename T>
void heapsort(T *array, int length)
{
    if (array == NULL || length <= 1)
    {
        return;
    }

    heapify(array, length);

    // now partition the array, in-place, into two: the heap and a partially-sorted array, like
    // [ head, ..., end-heap | ..., max ]
    // the 'end' heap is a moving pointer that starts from the end of the array, working backwards
    // until the heap portion of the array is consumed and what is left is an ordered array

    int end = length - 1;
    while (end > 0)
    {
        // swap the head of the heap (max of all keys in said heap) with the tail of the heap
        // and move the end index of the heap backward
        xchg(array, 0, end--);
        // essentially, we did a partial pop() operation on the heap, leaving the heap in
        // violation of its heap order, sinking the newly swapped head would restore it
        sink(array, 0, end);
    }
}

#endif

main.cpp

#include <iostream>

#include "heapsort.h"

using namespace std;

#ifdef USE_BOOST_UT

#define BOOST_TEST_DYN_LINK
#define BOOST_TEST_MODULE heapsort_test
#include <boost/test/unit_test.hpp>

BOOST_AUTO_TEST_CASE(heapsort_success)
{
    int unsorted[8] = {6, 5, 3, 1, 8, 7, 2, 4};
    int sorted[8]   = {1, 2, 3, 4, 5, 6, 7, 8};
    heapsort(unsorted, 8);
    BOOST_CHECK_EQUAL_COLLECTIONS(unsorted, unsorted+8, sorted, sorted+8);
}

BOOST_AUTO_TEST_CASE(heapsort_nullarray)
{
    int unsorted[2]  = {1, 0};
    int unchanged[2] = {1, 0};
    heapsort((int *) NULL, 0);
    heapsort(unsorted, 0);
    BOOST_CHECK_EQUAL_COLLECTIONS(unsorted, unsorted+2, unchanged, unchanged+2);
}

#else

int main()
{
    int unsorted[8] = {6, 5, 3, 1, 8, 7, 2, 4};

    heapsort(unsorted, 8);

    for (int i = 0; i < 8; i++)
    {
        cout << unsorted[i] << endl;
    }

    return 0;
}

#endif

Makefile

CC = gcc
CFLAGS = -Wall -g -x c++
LFLAGS = -lstdc++ -lm -lboost_unit_test_framework
DEFINES = -D TOPDOWN -D USE_BOOST_UT

OBJDIR = obj
BINDIR = bin

TARGET = main

all: $(TARGET)

$(TARGET): heapsort.h $(TARGET).cpp
	mkdir -p $(OBJDIR)
	$(CC) $(CFLAGS) $(DEFINES) -c $(TARGET).cpp -o $(OBJDIR)/$(TARGET).o

exe: $(TARGET)
	mkdir -p $(BINDIR)
	$(CC) $(OBJDIR)/$(TARGET).o $(LFLAGS) -o $(BINDIR)/$(TARGET)

run: exe
	./$(BINDIR)/$(TARGET)

valg: exe
	valgrind --leak-check=full -v ./$(BINDIR)/$(TARGET)

clean:
	rm -rf $(BINDIR) $(OBJDIR)