Heap, Heap Sort

Tags: [heap], [sort]

Solution:

def heap_sort(arr):
    if not arr:
        return arr

    heap = build_heap(arr)
    heap_size = len(heap)

    result = []
    for _ in xrange(len(heap)):
        result.append(heap_pop(heap, heap_size))
        heap_size -= 1

    return result

def build_heap(arr):
    if not arr:
        return arr

    size = len(arr)
    for i in xrange(((size - 1) - 1) / 2, -1, -1):
        heapify(arr, i, size)

    return arr

def heap_pop(heap, heap_size):
    if not heap_size:
        raise ValueError('heap is empty')

    root = heap[0]
    heap[0], heap[heap_size - 1] = heap[heap_size - 1], heap[0]

    heap_size -= 1
    heapify(heap, 0, heap_size)

    return root

def heapify(heap, index, heap_size):
    curr = heap[index]
    new_curr_index = index

    if 2 * index + 1 < heap_size:
        left = heap[2 * index + 1]
        if curr > left:
            curr, left = left, curr
            new_curr_index = 2 * index + 1

    if 2 * index + 2 < heap_size:
        right = heap[2 * index + 2]
        if curr > right:
            curr, right = right, curr
            new_curr_index = 2 * index + 2

    if index != new_curr_index:
        heap[index], heap[new_curr_index] = heap[new_curr_index], heap[index]
        heapify(heap, new_curr_index, heap_size)

if __name__ == '__main__':
    print 'Program is working'

    arr = [10, 1, 0, 10, 100, 1, 2, 3, 1]
    # arr = [1, 4, 10, 0, 3, 100]
    # arr = [10, 1, 10, 1, 0, 0, 1, 10]
    print arr

    result = heap_sort(arr)
    print result

    print 'Program is end'

Revelation:

• If our index is based on 0. If the index of current node is i, so the index of its left child should be 2 * i + 1, and the index of the right child should be 2 * i + 2.
• If our index is based on 0, If the index of current node is i, so the index of its parent should be (i - 1) / 2.
• When we build the heap, we build the heap from bottom to top, but why we didn't start from the last node in the array? Because we know the last node has no children, which means we don't need use heapify to adjust the nodes in that subtree. And all the nodes of the last level have no children, so we just need to start from the parent of the last node, which should be the last parent in the whole tree. The index of the last node is (size - 1), based on the above knowledge, if the index of the current node is i, so the index of its parent should be (i - 1) / 2. So the index of the last node is (size - 1), so the index of its parent is ((size - 1) - 1) / 2. (the index is based on 0, not 1).
• If the index is based on 1. If the index of the current node is i, so the index of its left child should be 2 * i, and the index of its right child should be 2 * i + 1. And the index of its parent should be i / 2.

Note:

• Time complexity to build a heap = O(n), n is the number of elements. reference: https://en.wikipedia.org/wiki/Binary_heap, reference: http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity
• Time complexity of heapify = O(lgn), n is the number of elements.
• Time complexity of heap sort = O(nlgn), n is the number of elements.