HeapSort implementations.

HeapSort.java

public class HeapSort {

    private static int parent(int idx) {
        return (idx - 1) / 2;
    }

    private static int left(int idx) {
        return 2 * idx + 1;
    }

    private static int right(int idx) {
        return 2 * idx + 2;
    }

    private static <T> void swap(T[] arr, int a, int b) {
        assert (a >= 0 && a < arr.length);
        assert (b >= 0 && b < arr.length);
        if (a == b) return;
        T temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    // variant 1: O(n log n) using iterative build-up of the heap
    private static <T extends Comparable<T>> void sort(T[] arr) {
        if (arr.length <= 1) return;

        heapify(arr);

        for (int end = arr.length - 1; end >= 1; end--) {
            swap(arr, 0, end);
            sink(arr, 0, end - 1);
        }
    }

    // given an unsorted array (representing a complete binary tree), max-heapify it
    private static <T extends Comparable<T>> void heapify(T[] arr) {
        // by iteratively "adding" new nodes, and then "bubbling" it up to its heap position
        for (int i = 1; i < arr.length; i++) {
            swim(arr, i);
        }
    }

    // assuming a valid heap at arr[0..end-1], place arr[end] where it belongs
    private static <T extends Comparable<T>> void swim(T[] arr, int end) {
        assert (end > 0);
        int parentIdx = parent(end);
        int idx = end;
        while (idx > 0) {
            if (arr[parentIdx].compareTo(arr[idx]) < 0) {
                swap(arr, parentIdx, idx);
                idx = parentIdx;
                parentIdx = parent(idx);
            } else {
                return;
            }
        }
    }

    // assuming an otherwise valid heap, except for its head, place arr[start] where it belongs
    private static <T extends Comparable<T>> void sink(T[] arr, int start, int end) {
        assert (start >= 0 && start < arr.length);
        assert (end >= 0 && end < arr.length);
        if (start == end) return;
        assert (end > start);

        int idx = start;
        while (idx < end) {
            int leftIdx = left(idx);
            int rightIdx = right(idx);
            int swapIdx = -1;
            // compare to left child: if left child exists and is bigger, that's the potential swap
            if (leftIdx <= end && arr[idx].compareTo(arr[leftIdx]) < 0) {
                swapIdx = leftIdx;
            }
            // compare to right child: if right child exists and is bigger, AND...
            if (rightIdx <= end && arr[idx].compareTo(arr[rightIdx]) < 0) {
                // if the left child was a potential swap, and this right child is also bigger than that left child
                if (swapIdx > 0 && arr[swapIdx].compareTo(arr[rightIdx]) < 0) {
                    swapIdx = rightIdx;
                }
                // otherwise, stick with the left child to swap
            }
            // finally, swap with the biggest child of the two, and set the current index to the one we just swapped with
            if (swapIdx > 0) {
                swap(arr, idx, swapIdx);
                idx = swapIdx;
            } else {
                // cannot sink no further
                return;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] numbers = new Integer[10];
        numbers[0] = 8;
        numbers[1] = 9;
        numbers[2] = 10;
        numbers[3] = 1;
        numbers[4] = 3;
        numbers[5] = 5;
        numbers[6] = 4;
        numbers[7] = 2;
        numbers[8] = 7;
        numbers[9] = 6;

        HeapSort.sort(numbers);
        for (int i = 0; i < numbers.length; i++) {
            System.out.println(numbers[i]);
        }
    }

}

heapsort.py

def _parent(idx):
    return (idx - 1) / 2

def _left(idx):
    return 2 * idx + 1

def _right(idx):
    return 2 * idx + 2

def _swap(arr, i, j):
    assert 0 <= i < len(arr)
    assert 0 <= j < len(arr)
    if i == j: return
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

def heapsort(arr):
    """Perform in-place heapsort, using the bottoms-up approach.

    """
    if len(arr) <= 1: return
    _heapify(arr)
    end = len(arr) - 1
    while end > 0:
        _swap(arr, 0, end)
        _sink(arr, 0, end - 1)
        end -= 1

def _heapify(arr):
    """Heapify the given array in-place.

    Here, we're producing a max-heap.

    """
    end = len(arr) - 1
    # start from the right-most parent node
    idx = _parent(end)
    while idx >= 0:
        _sink(arr, idx, end)
        idx -= 1

def _sink(arr, start, end):
    """Given a heap that is otherwise valid except maybe for its head,
    sink this node at the head to its appropriate position.

    """
    assert 0 <= start < len(arr)
    assert 0 <= end < len(arr)
    if start == end: return
    assert start < end
    idx = start
    while idx < end:
        lx = _left(idx)
        rx = _right(idx)
        swap = None
        if lx <= end and arr[idx] < arr[lx]:
            swap = lx
        if rx <= end and arr[idx] < arr[rx]:
            if arr[rx] > arr[lx]:
                swap = rx
        if swap is None:
            return
        _swap(arr, idx, swap)
        idx = swap


if __name__ == '__main__':
    # for quick debugging / sanity checking
    numbers = [ 8, 9, 10, 1, 3, 5, 4, 2, 7, 6 ]
    heapsort(numbers)
    for n in numbers:
        print n

heapsort_test.py

import unittest
from heapsort import heapsort


class SortTest(unittest.TestCase):

    def test_empty(self):
        arr = []
        heapsort(arr)
        self.assertEqual([], arr)

    def test_one_item(self):
        arr = [1]
        heapsort(arr)
        self.assertEqual([1], arr)

    def test_two_items(self):
        for arr in [[1,2], [2,1]]:
            heapsort(arr)
            self.assertEqual([1,2], arr)

    def test_three_items(self):
        for arr in [[1,2,3], [3,2,1], [2,1,3]]:
            heapsort(arr)
            self.assertEqual([1,2,3], arr)

    def test_odd_many_items(self):
        for arr in [
                [1,2,3,4,5,6,7,8,9],
                [5,9,7,1,2,4,6,3,8],
                   ]:
            heapsort(arr)
            self.assertEqual([1,2,3,4,5,6,7,8,9], arr)

    def test_even_many_items(self):
        for arr in [
                [1,2,3,4,5,6,7,8,9,10],
                [5,9,7,1,2,10,4,6,3,8],
                   ]:
            heapsort(arr)
            self.assertEqual([1,2,3,4,5,6,7,8,9,10], arr)

    def test_many_many_items(self):
        sorted = [x for x in range(10000)]
        for arr in [
                [x for x in xrange(10000)],
                [x for x in xrange(10000-1, -1, -1)],
                   ]:
            heapsort(arr)
            self.assertEqual(sorted, arr)


if __name__ == '__main__':
    unittest.main()