heap_sort

heap_sort.py

# coding=utf-8

import random
import math


def max_heapify(A, index):
    left_index = index * 2
    right_index = left_index + 1

    if left_index < len(A) and A[left_index] > A[index]:
        largest_index = left_index
    else:
        largest_index = index

    if right_index < len(A) and A[right_index] > A[largest_index]:
        largest_index = right_index

    if largest_index != index:
        A[index], A[largest_index] = A[largest_index], A[index]
        max_heapify(A, largest_index)


def build_max_heap(A):
    for i in reversed(range(math.ceil(len(A) / 2))):
        max_heapify(A, i)


def heap_sort(A):
    ret = []
    while len(A):
        build_max_heap(A)
        ret.append(A[0])
        A = A[1:]
    return list(reversed(ret))


if __name__ == '__main__':
    unsorted = random.sample(range(1, 10000), 100)
    print('unsorted: %s' % unsorted)

    sorted = heap_sort(unsorted)
    print('sorted: %s' % sorted)