#=======================================================================
# 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." )
