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

heap sort

Python, 32 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
27
28
29
30
31
32
def HeapSort(A):
    def heapify(A):
        start = (len(A) - 2) / 2
        while start >= 0:
            siftDown(A, start, len(A) - 1)
            start -= 1

    def siftDown(A, start, end):
        root = start
        while root * 2 + 1 <= end:
            child = root * 2 + 1
            if child + 1 <= end and A[child] < A[child + 1]:
                child += 1
            if child <= end and A[root] < A[child]:
                A[root], A[child] = A[child], A[root]
                root = child
            else:
                return

    heapify(A)
    end = len(A) - 1
    while end > 0:
        A[end], A[0] = A[0], A[end]
        siftDown(A, 0, end - 1)
        end -= 1

if __name__ == '__main__':
    
    T = [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10] 

    HeapSort(T)
    print T

1 comment

mitnk king (author) 11 years, 9 months ago  # | flag

import heapq

def HeapSort2(A): heap = list(A) heapq.heapify(heap) for i in range(len(A)): A[i] = heapq.heappop(heap)

if __name__ == '__main__': T = [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10] HeapSort(T) print T

Created by mitnk king on Thu, 4 Mar 2010 (MIT)
Python recipes (4591)
mitnk king's recipes (3)

Required Modules

  • (none specified)

Other Information and Tasks