Heap Sort

# https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

# 25 45 1 66 14 19
# 1. Convert this array into a complete binary tree:
#     25
#    /   \
#   45    1
#   /\   /
# 66 14 19
# 2. Convert this complete binary tree into heap using the heapify function
# 3. Swap the root node with the leaf node at the end

# Build a heap from arr with size n
def heapify(arr, n, root):
	largest = root
	l = 2 * root + 1
	r = 2 * root + 2

	if l < n and arr[root] < arr[l]:
		largest = l

	if r < n and arr[largest] < arr[r]:
		largest = r

	if largest != root:
		(arr[root], arr[largest]) = (arr[largest], arr[root])
        # Recursively heapify the affected sub-tree 
		heapify(arr, n, largest)


def heapSort(arr):
	n = len(arr)
    # Build heap (rearrange array)
    # Starting from the last non-leaf node and heapify each node
	for i in range(n // 2, -1, -1):
		heapify(arr, n, i)

    # extract the bigger element one by one
	for i in range(n - 1, 0, -1):
        # Swap current root with end
		(arr[i], arr[0]) = (arr[0], arr[i])
        # call max heapify on the reduced heap
		heapify(arr, i, 0)


arr = [12, 11, 13, 5, 6, 7, ]
print(arr)
heapSort(arr)
print(arr)

# [12, 11, 13, 5, 6, 7]
# [5, 6, 7, 11, 12, 13]