heap sort

heap_sort.py

#coding:UTF-8

def heapify(arr, i):
    # O(lgn)
    left_idx = 2*i+1
    if left_idx >= len(arr):
        return
    right_idx = left_idx + 1
    if right_idx >= len(arr):
        left = arr[left_idx]
        if left > arr[i]:
            arr[i], arr[left_idx] = arr[left_idx], arr[i]
    else:
        left = arr[left_idx]
        right = arr[right_idx]
        cur = arr[i]

        if left > right:
            m = left
            m_idx = left_idx
        else:
            m = right 
            m_idx = right_idx

        if cur < m:
            arr[i], arr[m_idx] = arr[m_idx], arr[i]
            heapify(arr, m_idx)


def build_max_heap(arr):
    # O(n)
    for i in range(len(arr)//2, -1, -1):
        heapify(arr, i)

def heap_sort(arr):
    # O(nlgn)
    max_heap = build_max_heap(arr)
    s = []
    while arr:
        arr[0], arr[-1] = arr[-1], arr[0]
        s.append(arr[-1])
        del arr[-1]
        heapify(arr, 0)
    return s

import random
x = [random.randint(0, 100) for i in range(10)]
print("input: ", x)
s = heap_sort(x)
print("sorted: ", s)