Heap sort

Introduction

In this algorithm we will use a priority queue to sort the array. We can use any priority queue to develop a sorting algorithm. In fact, we can see how some already known sorting algorithms are related to priority queues:

Selection sort: Use a priority queue represented as an unordered array.
Insertion sort: Use a priority queue represented as an ordered array.

For the heapsort we will use a priority queue represented as a heap. The canonical implementation is to insert all items into a minimum-oriented priority queue and repeteadly remove the root, which will always be the minimum element of those that are still on the heap.

Algorithm

For starters, this is an implementation of a minimum-ordered priority queue using a binary heap (heap-ordered binary tree represented in level order in an array):

class MinPriorityQueue(object):
    """Minimum-oriented priority queue."""

    def __init__(self):
        self.pq = []

    def __repr__(self):
        return "{}".format(self.pq)

    def size(self):
        return len(self.pq)

    def is_empty(self):
        return self.pq == []

    def insert(self, key):
        self.pq.append(key)
        self.swim(self.size() - 1)

    def delete_min(self):
        if self.is_empty():
            return

        minimum = self.pq.pop(0)
        if self.is_empty():
            return minimum

        last = self.pq.pop()
        self.pq = [last] + self.pq
        self.sink(0)

        return minimum

    def swim(self, k):
        while (k != 0) and (self.pq[k] < self.pq[(k-1)//2]):
            node = k
            parent = (k-1)//2
            self.pq[node], self.pq[parent] = self.pq[parent], self.pq[node]
            k = parent

    def sink(self, k):

        def left_child(k):
            return 2*k + 1

        def has_left_child(k):
            return (2*k + 1) < self.size()

        def right_child(k):
            return 2*k + 2

        def has_right_child(k):
            return (2*k + 2) < self.size()

        while has_left_child(k):
            j = left_child(k)
            if has_right_child(k) and (self.pq[right_child(k)] < self.pq[left_child(k)]):
                j = right_child(k)

            node = k
            child = j
            if self.pq[node] < self.pq[child]:
                break
            else:
                self.pq[node], self.pq[child] = self.pq[child], self.pq[node]
                k = child

And with this priority queue it is really easy to implement the heap sort:

def heap(a):
    """
    Implements the heap sort algorithm.
    """

    pq = MinPriorityQueue()
    for elem in a:
        pq.insert(elem)

    a = []
    elem = pq.delete_min()
    while elem is not None:
        a.append(elem)
        elem = pq.delete_min()

    return a

We insert all elements of the array in the priority queue and continiously remove the top of the heap. As the heap has operations to keep the minimum element always on top we don’t need to care about anything else.

Complexity analysis

Time

When we insert the elements of the array into the priority queue, we are doing O(N) = N · log N compares.

When we delete the minimum element of the heap, we are doing O(N) = N · log N compares.

So the cost is: O(N) = 2N · log N.

Space

We build a heap that contains as much elements as the array, so the cost is O(N) = N + N = 2N.

The space can be reduced to N if we take the array and use it directly as the binary heap. To do so, we must:

Use the array as a maximum-oriented priority queue.
Sink all elements in the left half of the array. We must start at N/2 and go back to the first element.
Take the heap’s top (maximum element), exchange positions with the last element of the array, and sink the new top.
Take the heap’s top (second to maximum), exchange positions with the last - 1 element of the array and sink the new top.
etc