ヒープソートについて
概要
- 二分ヒープ木を用いてソートを行うアルゴリズム
動作
- 未整列のリストから要素を取り出し、順にヒープに追加
- ルート（最大値または最小値)を取り出し、整列済みリストに追加
- 動作範囲を制限して1に戻る
実装
def heapify(arr, max_n, i):
# 最大の値を持つindexを探し先頭に持ってくる
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < max_n and arr[i] < arr[l]:
largest = l
if r < max_n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, max_n, largest)
def hsort(arr):
n = len(arr)
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# heapifyで先頭が最大値になっているので末尾に持ってくる
arr[i], arr[0] = arr[0], arr[i]
# heapifyで最大値を先頭に
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
print(arr) # [1, 12, 9, 5, 6, 10]
hsort(arr)
print(arr) # [1, 5, 6, 9, 10, 12]