#
Heap Sort In Python

#======================================================================= # Author: Isai Damier # Title: Heapsort # Project: geekviewpoint # Package: algorithms # # Statement: # Given a disordered list of integers (or any other items), # rearrange the integers in natural order. # # Sample Input: [8,5,3,1,9,6,0,7,4,2,5] # Sample Output: [0,1,2,3,4,5,5,6,7,8,9] # # Time Complexity of Solution: # Best O(nlog(n)); Average O(nlog(n)); Worst O(nlog(n)). # # Approach: # Heap sort happens in two phases. In the first phase, the array # is transformed into a heap. A heap is a binary tree where # 1) each node is greater than each of its children # 2) the tree is perfectly balanced # 3) all leaves are in the leftmost position available. # In phase two the heap is continuously reduced to a sorted array: # 1) while the heap is not empty # - remove the top of the head into an array # - fix the heap. # Heap sort was invented by John Williams not by B. R. Heap. # # MoveDown: # The movedown method checks and verifies that the structure is a heap. # # Technical Details: # A heap is based on an array just as a hashmap is based on an # array. For a heap, the children of an element n are at index # 2n+1 for the left child and 2n+2 for the right child. # # The movedown function checks that an element is greater than its # children. If not the values of element and child are swapped. The # function continues to check and swap until the element is at a # position where it is greater than its children. #======================================================================= def heapsort( aList ): # convert aList to heap length = len( aList ) - 1 leastParent = length / 2 for i in range ( leastParent, -1, -1 ): moveDown( aList, i, length ) # flatten heap into sorted array for i in range ( length, 0, -1 ): if aList[0] > aList[i]: swap( aList, 0, i ) moveDown( aList, 0, i - 1 ) def moveDown( aList, first, last ): largest = 2 * first + 1 while largest <= last: # right child exists and is larger than left child if ( largest < last ) and ( aList[largest] < aList[largest + 1] ): largest += 1 # right child is larger than parent if aList[largest] > aList[first]: swap( aList, largest, first ) # move down to largest child first = largest; largest = 2 * first + 1 else: return # force exit def swap( A, x, y ): tmp = A[x] A[x] = A[y] A[y] = tmp

import unittest from algorithms import sorting class Test( unittest.TestCase ): def testHeapsort( self ): A = [8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5] sorting.heapsort( A ) for i in range( 1, len( A ) ): if A[i - 1] > A[i]: self.fail( "heapsort method fails." )