《アルゴリズムを学ぶ》21.ヒープソート

Overview

ヒープソート（Heap Sort） は、ヒープ（Heap）を利用して $O(N log N)$で動作するソートアルゴリズム 。ヒープを使って最大（または最小）値を取り出しながら配列をソートする。
1.ヒープソートの基本概念
2.ヒープソートのアルゴリズム
3.ヒープソートの応用
4.典型問題を解いてみる

1. ヒープソートの基本概念

ヒープソートは以下の2つのステップで構成される：
1. 配列をヒープ（完全二分木）に変換
2. ヒープの最大（または最小）値を取り出して、ソートを完了させる

(1) ヒープソートの特徴

• 計算量：$O(N log N)$
  ヒープの構築($O(N）$) + ヒープ操作($O(log N)$を N 回）

• 安定性：非安定ソート
  同じ値の要素が、元の順番と異なる順番で出力される可能性がある

• メモリ使用量：$O(1)$（配列内での操作のみ）
  追加の配列を使わず、内部でヒープ操作を行う

• 最悪計算量 $O(N log N)$ を保証
  クイックソート（Quick Sort）は最悪 $O(N^2)$ の可能性があるが、ヒープソートは $O(N log N)$ で安定

2. ヒープソートのアルゴリズム

(1) 配列をヒープに変換（Heapify）

• 完全二分木の形を作り、最大ヒープ（または最小ヒープ）を構築
• 子ノードが親ノードより大きくならないように調整
• ヒープ構築の計算量：$O(N)$

def heapify(arr, n, i):
    largest = i  # 親ノード
    left = 2 * i + 1  # 左の子
    right = 2 * i + 2  # 右の子
    
    # 左の子が親より大きければ更新
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 右の子が親より大きければ更新
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 親ノードが最大でない場合、交換して再帰的に調整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

(2) ヒープソートの実装

• ヒープを構築した後、ルート（最大値）を取り出して整列
• ヒープサイズを縮小しながら、残りの部分を再調整

def heap_sort(arr):
    n = len(arr)

    # 1. 配列をヒープ化（最大ヒープを作成）
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 2. ヒープの最大要素を取り出し、配列末尾と交換しながらソート
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 最大値を末尾に移動
        heapify(arr, i, 0)  # 残りのヒープを調整

# 使用例
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr)  # 出力: [1, 3, 4, 5, 10]

• 計算量: O(N log N)
  • ヒープ構築：O(N)
  • ヒープから要素を削除して再構築：O(log N) を N 回実行 → O(N log N)

3. ヒープソートの応用

(1) K 番目に小さい要素を求める

ヒープを使えば、配列内の K 番目の最小値を効率的に取得 できる。

import heapq

arr = [7, 10, 4, 3, 20, 15]
k = 3

heapq.heapify(arr)  # ヒープ化
for _ in range(k - 1):
    heapq.heappop(arr)  # k-1 回最小値を取り出す

print(heapq.heappop(arr))  # 3番目に小さい値（7）

• O(N + K log N) で求められる

(2) 大量データのソート

• 通常のソートより、O(N log N) で安定した性能を発揮
• 追加メモリを使用しないため、大規模データに向いている

4. 典型問題を解いてみる

例題1. ヒープソートの実装

問題: N 個の整数をヒープソートでソートせよ。

参考： ABC315 B - Heap Sort

回答　

N = int(input())
arr = list(map(int, input().split()))

heap_sort(arr)
print(*arr)

例題2. K 番目に小さい要素を求める

問題: N 個の整数 A から K 番目に小さい値を求めよ。

参考： ABC318 B - Kth Smallest Element

回答　

import heapq

N, K = map(int, input().split())
A = list(map(int, input().split()))

heapq.heapify(A)
for _ in range(K - 1):
    heapq.heappop(A)

print(heapq.heappop(A))

例題3. 優先度付きキューのシミュレーション

問題: N 個のクエリが与えられる。insert x で x を追加し、pop で最小値を取り出せ。

参考： ABC319 C - Priority Queue

回答　

import heapq

N = int(input())
heap = []

for _ in range(N):
    query = input().split()
    if query[0] == "insert":
        heapq.heappush(heap, int(query[1]))
    elif query[0] == "pop":
        print(heapq.heappop(heap))