# Heap: a Binary Tree (implemented via an array), either a MaxHeap (largest root) or MinHeap (smallest root)
# Constraint: a[k] <= a[ 2*k+1 ] and a[k] <= a[ 2*k+2 ] (parent is less than it's children)
# Fast (array based, supports in place sorting) and flexible it can support things like Schedulers,
# finding the min, max, median, or kth element in O(1) time, or in Graph Algorithms
# Heapsort O(n log(n))
class Node( object ):
def __init__( self , key ):
self.key = key
class HeapSort( object ):
def __init__( self ):
self.heap = []
def heapify( self, A ):
self.heap = A
start = ( len(A) - 2) / 2
while start >= 0:
self.sift_down( A, start, len(A) - 1)
start -= 1
def sift_down( self, A, start, end ):
current = start
while current * 2 + 1 <= end: # at least one child
child = current * 2 + 1 # left child
if child + 1 <= end and A[child] < A[child + 1]: # right child is largest
child += 1
if child <= end and A[current] < A[child]: # parent compared to largest
A[current], A[child] = A[child], A[current] # swap so largest is parent
current = child
else:
return
def insert( self, key ):
""" add to the end of the heap, then fix to the constraint """
self.heap.append( key )
self.heapify( self.heap )
def pop( self ):
""" remove the root, then make the last element the new root, then fix the constraint """
self.heap[0], self.heap[ len( self.heap ) -1 ] = self.heap[ len( self.heap ) -1 ], self.heap[0] # swap so max now at the end
max = self.heap.pop() # extract the last value and reduce the list size
# self.sift_down( self.heap, 0, len( self.heap) -1 )
self.heapify( self.heap ) # enforce the constraint
return max
if __name__ == '__main__':
a = [ 20, 14, 17, 8, 6, 9, 4, 1, 15 ]
heapSort = HeapSort()
heapSort.heapify( a )
print heapSort.heap
print 'sorted: ',
print heapSort.pop(),
print heapSort.heap
while len( heapSort.heap ) > 0:
print heapSort.pop(),
print
b = [ 6, 5, 3, 1, 8, 7, 2, 4 ]
heapSort.heapify( b )
print heapSort.heap
print 'sorted: ',
while len( heapSort.heap ) > 0:
print heapSort.pop(),