SKHeap; A quick MaxHeap and HeapSort implementation

Heap is an interesting data structure. It is a binary tree, that keeps the maximum (in case of MaxHeap) element at the root, thus providing access to it in O(1) i.e. constant time. You can pop the root element in O(lgN) time, and insert new elements into the heap in O(lgN) time as well. Initial buildup of the heap takes linear time. You can sort a sequence of elements using heap, by first building the heap out of all the elements, and then retrieve the elements back. Since initial build up is linear time, each retrieval of the maximum element is O(lgN) time, and you do N such retrievals, the resulting sorting algorithm is of O(NlgN) complexity and called HeapSort.

It is fun to implement these well known data structures and algorithms. So while I was bored and free for half an hour, I quickly wrote a basic implementation of a Heap and HeapSort in Objective-C and pushed it to Github. Check it out and let me know if you like it or find any issues with it.

Be Sociable, Share!

Leave a Reply