ヒープソートは、最大ヒープと呼ばれる特殊なデータ構造を使用します。最大ヒープは、要素が親ノードよりも大きいという条件を満たす二分木です。ヒープソートでは、まずソート対象の配列を最大ヒープに変換し、その後、最大ヒープから最大値を順に取り出してソート済みの配列を作成します。
以下に、ヒープソートの基本的な手順を示します。
- ソート対象の配列を最大ヒープに変換する（ヒープ化）。
- 最大ヒープから最大値を取り出し、ソート済みの配列に追加する。
- ヒープのサイズを1つ減らして、ヒープを再構築する。
- ヒープのサイズが1より大きい場合、手順2に戻る。
ヒープソートは、最悪時間計算量がO(n log n)であり、一般的に高速なソートアルゴリズムとされています。以下に、Pythonでのヒープソートの実装例を示します。
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
# 使用例
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)このコードは、与えられた配列をヒープソートによって昇順にソートします。ヒープソートの基本的なアイデアと、再帰的なheapify関数の使い方が分かるかと思います。
ヒープソートは、大量のデータを効率的にソートするための強力なツールです。ビッグO記法とヒープソートの理解を深めることで、さまざまなアルゴリズムやデータ構造に応用することができます。