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

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)

### Tags

• (none)
▶ Show machine tags (4)

### Required Modules

• (none specified)