heapsort.py

#!/usr/bin/python
''' 
heapsort 
from : https://en.wikipedia.org/wiki/Heapsort#Pseudocode
'''

def heapsort(a):
    ''' input : an unordered array a'''
    count = len(a)
    # first place a in max-heap order
    heapify(a)
    end = count-1  # for zero-based arrays, the chiledren are 2*i+1 / 2*i+2
    while end > 0:
        # swap the root(maximum value) of the heap 
        # with tha last element of the heap.
        swap(a, end, 0)
        # decrease the size of the heap by one
        # so that the previous max value will stay in its proper placement
        end = end-1
        # put the heap back in max-heap order
        siftdown(a, 0, end)

def heapify(a):
    count = len(a)
    start = (count - 2)//2 # the index in a of the last parent node.
    
    while start >= 0:
        # sift down the node at index start to the proper place
        # such that all nodes below the start index are in heap order.
        siftdown(a, start, count-1)
        start = start -1

def siftdown(a, start, end):
    ''' end: represents the limit of how far down the heap to sift.'''
    root = start
    while root*2 + 1 <= end: # while the root has at least one child
        child = root*2 + 1 # the left child
        swap_target = root # keeps track of child to swap with
        if a[swap_target] < a[child]:  # if root is smaller than left child:
            swap_target = child
        if child+1 <= end and a[swap_target] < a[child+1]:
            # if right child exists and it's begger than 
            # what we're currently swapping with
            # ( max(root, left_child) )
            swap_target = child + 1
        
        if swap_target != root: # if we need to swap at all
            swap(a, root, swap_target)
            root = swap_target
            # repeat to continue sifting down the child now
        else:
            return


def swap(li, index1, index2):
    li[index1], li[index2] = li[index2], li[index1]


import random
def test():
    a=range(10)
    random.shuffle(a)
    print a
    heapsort(a)
    print a

test()