heap_sort.py

def max_heap_sort(arr):
    """ Heap Sort that uses a max heap to sort an array in ascending order
        Complexity: O(n log(n))
    """
    for i in range(len(arr)-1,0,-1):
        max_heapify(arr, i)
        
        temp = arr[0]
        arr[0] = arr[i]
        arr[i] = temp

	
def max_heapify(arr, end):
    """ Max heapify helper for max_heap_sort
    """
    last_parent = int((end-1)/2)

    # Iterate from last parent to first
    for parent in range(last_parent,-1,-1):
        current_parent = parent

        # Iterate from current_parent to last_parent
        while current_parent <= last_parent:
            # Find greatest child of current_parent
            child = 2*current_parent + 1
            if child + 1 <= end and arr[child] < arr[child+1]:
                child = child + 1

            # Swap if child is greater than parent
            if arr[child] > arr[current_parent]:
                temp = arr[current_parent]
                arr[current_parent] = arr[child]
                arr[child] = temp

                current_parent = child
            # If no swap occured, no need to keep iterating
            else:
                break
		

def min_heap_sort(arr):
    """ Heap Sort that uses a min heap to sort an array in ascending order
        Complexity: O(n log(n))
    """
    for i in range(0, len(arr)-1):
        min_heapify(arr, i)
	

def min_heapify(arr, start):
    """ Min heapify helper for min_heap_sort
    """
    # Offset last_parent by the start (last_parent calculated as if start index was 0)
    # All array accesses need to be offet by start
    end = len(arr)-1
    last_parent = int((end-start-1)/2)

    # Iterate from last parent to first
    for parent in range(last_parent,-1,-1):
        current_parent = parent

        # Iterate from current_parent to last_parent
        while current_parent <= last_parent:
            # Find lesser child of current_parent
            child = 2*current_parent + 1
            if child + 1 <= end-start and arr[child+start] > arr[child+1+start]:
                child = child + 1

            # Swap if child is less than parent
            if arr[child+start] < arr[current_parent+start]:
                temp = arr[current_parent+start]
                arr[current_parent+start] = arr[child+start]
                arr[child+start] = temp

                current_parent = child
            # If no swap occured, no need to keep iterating
            else:
                break

if __name__ == '__main__':
	import timeit

	array = [1,5,65,23,57,1232,-1,-5,-2,242,100,4,423,2,564,9,0,10,43,64]
	print("array:")
	print(array)
	print("Max Heapify:")
	max_heap_sort(array)
	print(array)
	array = [1,5,65,23,57,1232,-1,-5,-2,242,100,4,423,2,564,9,0,10,43,64]
	print("Min Heapify:")
	min_heap_sort(array)
	print(array)
	print("Max Heapify Time:", timeit.timeit('max_heap_sort(array)', setup="from __main__ import max_heap_sort, array",number=10000))
	print("Min Heapify Time:", timeit.timeit('min_heap_sort(array)', setup="from __main__ import min_heap_sort, array",number=10000))