Min-Heap as a sorting algorithm

#1

I finished the min-heap module with little sense of what it really was, so I went back for another look. A min-heap is an efficient method for creating a list in such a way that the minimum element is always instantly accessible without a search, and in popping that minimum, the next minimum rises (also efficiently) to the top.

It occurred to me that this could be used in a sorting algorithm: from the list you want sorted, append each item to the heap, then pop each item into a new list (or the same one, if you want to sort in place.)

Since the heap is based on a binary tree, for a list of n elements, if n is equal to 2^k for some k, the tree is k elements high. Thus the maximum number of swaps to go up or down the tree is k or log(n).

Since you need to go through the list twice (once for append and once for pop), and since each step can involve a maximum of log(n) additional steps, the time for my sort should increase as approximately 2nlog(n).

So … I decided to compare with an implementation of merge sort (known to sort in n*log(n) ) from a different course, and compare the times.

The heap_sort() function (sort-in-place version) is:

def heap_sort(lst):
    min_heap = MinHeap()
    while lst:  
      min_heap.add(lst.pop())
           # remove minimum until min_heap is empty
    while min_heap.count != 0:
      lst.append(min_heap.retrieve_min())

… and when run alongside merge_sort() using the timeit module for timing, we see:

You can see that heap_sort follows n*log(n) closely, running linearly slower (up to 3x) than merge_sort. Interestingly, it looks as though somewhere between a list length of 10^5 and 10^6, heap_sort becomes faster than merge_sort, probably (I say with absolutely no authority!) due to inefficiencies inherent in recursion.

4 Likes
FAQ: Heaps: Python - Min-Heap Review