Welcome, guest | Sign In | My Account | Store | Cart

a python version of heap sort

Python, 26 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def heapify(array, start, end, cmp): # array is almost a heap (except the root)
    root = start
    while root * 2 + 1 < end:
        child = root * 2 + 1
        if child + 1 < end:
            v, k = cmp((array[root], root), (array[child], child), (array[child + 1], child + 1))
        else:
            v, k = cmp((array[root], root), (array[child], child))
        if not k == root:
            array[root], array[k] = array[k], array[root]
            root = k
        else:
            break

def build_heap_max(array):
    length = len(array)
    for i in xrange(length / 2, -1, -1):
        heapify(array, i, length, max)

def heap_sort(array):
    build_heap_max(array)
    size = len(array)
    while size > 0:
        array[0], array[size - 1] = array[size - 1], array[0]
        heapify(array, 0, size - 1, max)
        size -= 1

1 comment

Matteo Dell'Amico 10 years, 6 months ago  # | flag

For a heap implementation, look no farther than heap.py in the standard library. :)

Created by huang chongdi on Thu, 12 May 2011 (MIT)
Python recipes (4591)
huang chongdi's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks