ヒープソートとは？#

ヒープソートは以下のような特徴を持つソートアルゴリズムです：

動作原理:
- ヒープと呼ばれる特殊な二分木構造を利用します。
- 配列をヒープ構造に変換し、そこから最大値または最小値を順に取り出してソートします。
アルゴリズムの流れ:
- 未整列の配列からヒープ構造を構築します（通常は最大ヒープ）。
- ヒープの根（最大値）を配列の末尾と交換し、ヒープサイズを1減らします。
- 根から始めてヒープ構造を再構築します。
- これを繰り返し、全要素をソートします。
特徴:
- 計算時間の複雑さは常に O(n log n) です。
- インプレースソートであり、追加のメモリをほとんど必要としません。
- 安定ソートではありません（同値要素の相対的な順序が保たれない）。

インプレースソート(In-place sort)とは

利点:
- 最悪、平均、最良のケースでも O(n log n) の時間計算量を保証します。
- 追加のメモリ空間をほとんど必要としません。
欠点:
- キャッシュ効率が悪く、実際の実行時間では他のO(n log n)アルゴリズムより遅いことがあります。
- 安定ソートではないため、同値要素の順序が重要な場合は適していません。
応用:
- 優先度付きキューの実装に使用されます。
- 部分ソート（k個の最大/最小要素の抽出）に効率的です。

ヒープソートは、その保証された時間計算量と省メモリ性から、特に大規模データセットや制約のあるメモリ環境でのソートに適しています。

コード例#

ヒープソートのPythonによる具体的な実装例を以下に示します：

1
def heapify(arr, n, i):
2
    largest = i
3
    left = 2 * i + 1
4
    right = 2 * i + 2
5

6
    if left < n and arr[left] > arr[largest]:
7
        largest = left
8

9
    if right < n and arr[right] > arr[largest]:
10
        largest = right
11

12
    if largest != i:
13
        arr[i], arr[largest] = arr[largest], arr[i]
14
        heapify(arr, n, largest)
15

16
def heap_sort(arr):
17
    n = len(arr)
18

19
    # ヒープを構築
20
    for i in range(n // 2 - 1, -1, -1):
21
        heapify(arr, n, i)
22

23
    # 要素を1つずつ取り出す
24
    for i in range(n - 1, 0, -1):
25
        arr[0], arr[i] = arr[i], arr[0]
26
        heapify(arr, i, 0)
27

28
# 使用例
29
arr = [12, 11, 13, 5, 6, 7]
30
print("ソート前:", arr)
31

32
heap_sort(arr)
33
print("ソート後:", arr)

このコードを実行すると、以下のような出力が得られます：

1
ソート前: [12, 11, 13, 5, 6, 7]
2
ソート後: [5, 6, 7, 11, 12, 13]

この実装の主な特徴は以下の通りです：

heapify関数：
- 指定されたノードから始まる部分木を最大ヒープに変換します。
- 親ノードと子ノードを比較し、必要に応じて交換します。
heap_sort関数：
- まず、配列全体を最大ヒープに変換します。
- その後、ヒープの根（最大値）を配列の末尾と交換し、ヒープサイズを減らしながら再度heapifyを行います。
ソートプロセス：
- 最初に最大ヒープを構築することで、最大値が常に根に来るようにします。
- その後、最大値を順次取り出して配列の末尾から格納していきます。

「heap」という英単語の意味#

山や積み重ねを指します。物が乱雑に積み重なっている様子を表します。具体的には、石、砂、本、衣服など、さまざまな物が対象となります。

挿入ソートまとめ

PHPのリファレンスとCのポインタの違い