Algorithm:heap sort in pythonアルゴリズム導論スタックソート
2668 ワード
An Python implementation of heap-sort
based on the detailed algorithm description in Introduction to Algorithms Third Edition
based on the detailed algorithm description in Introduction to Algorithms Third Edition
import random
def max_heapify(arr, i, length):
while True:
l, r = i * 2 + 1, i * 2 + 2
largest = l if l < length and arr[l] > arr[i] else i
if r < length and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest], i = arr[largest], arr[i], largest
else:
break
def build_heap(arr):
for i in range(len(arr) / 2, -1, -1):
max_heapify(l, i, len(arr))
def heap_sort(arr):
build_heap(arr)
length = len(arr)
for i in range(1, length):
arr[0], arr[-i] = arr[-i], arr[0]
max_heapify(arr, 0, length - i)
if __name__ == '__main__':
l = [random.randint(1, 113) for i in range(18)]
print l
heap_sort(l)
print l