ヒープの性質と配列表現
配列に格納された完全二分木の構造を理解し、親子のインデックス計算式を導き、sift-upとsift-down操作を可視化します。
「ヒープの性質と配列表現」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
ヒープとは
ヒープは、ヒープ条件を満たす特殊な完全二分木です。min-heap ではすべての親が子以下であり、max-heap ではすべての親が子以上です。この条件により、最小要素（または最大要素）が常にルートにあることが保証され、極値要素に O(1) でアクセスできます。ヒープは優先度付きキューの基盤となるデータ構造です。
# Min-heap example:
# 1
# / \
# 3 2
# / \ / \
# 7 4 5 6
# Every parent <= its children
# Root (1) is always the minimum
# Max-heap example:
# 9
# / \
# 7 8
# / \ / \
# 3 4 5 6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')完全二分木の構造
ヒープは完全二分木として格納されます。すべてのレベルが完全に埋まっていますが、最後のレベルだけは例外として、左から右に埋められます。この構造により、無駄な領域やポインターを必要としない、効率的な配列表現が可能になります。完全二分木の性質により、ヒープの高さは常に floor(log₂ n) となるため、push と pop の操作が O(log n) であることが保証されます。
# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))
# NOT complete (last level not left-filled):
# 1
# / \
# 2 3
# \
# 4 <- right child without left sibling
# Valid complete binary tree with 4 nodes:
# 1
# / \
# 2 3
# /
# 4
print('Complete BT: height = floor(log2(n)) always')ヒープの配列表現
完全二分木の構造により、ヒープはポインターなしの単純な配列に格納できます。インデックス i（0 始まり）のノードについて、親は (i-1) // 2、左の子は 2i+1、右の子は 2i+2 にあります。この整数演算によってポインターの走査が不要になり、ヒープは非常にキャッシュ効率のよい構造になります。
# Array representation (0-indexed):
# Index: 0 1 2 3 4 5 6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree: 1 (index 0)
# / \
# 3 2 (indices 1, 2)
# / \ / \
# 7 4 5 6 (indices 3,4,5,6)
# Index formulas (0-based):
def parent(i): return (i - 1) // 2
def left_child(i): return 2 * i + 1
def right_child(i): return 2 * i + 2
heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])シフトアップ：挿入後のヒープの復元
シフトアップ（bubble-up または heapify-up とも呼ばれます）は、新しい要素をヒープ配列の末尾に挿入した後に使用します。新しい要素とその親を比較し、ヒープ条件に違反していれば交換して上方向に処理を続けます。要素が正しい位置に入るか、ルートに到達するまで繰り返します。木の高さが O(log n) であるため、この処理は O(log n) で実行されます。
def sift_up(heap, i):
while i > 0:
p = (i - 1) // 2 # parent index
if heap[p] > heap[i]: # min-heap: parent should be smaller
heap[p], heap[i] = heap[i], heap[p]
i = p
else:
break # heap property restored
# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0) # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap) # 0 should bubble to rootシフトダウン：取り出し後のヒープの復元
シフトダウン（heapify-down）は、ルートを削除した後に使用します。最後の要素をルートに移動し、小さい方の子（min-heap の場合）と繰り返し交換して下へ移動させ、ヒープ条件を復元します。これも O(log n) で実行されます。シフトアップとシフトダウンは、すべてのヒープ操作の基本要素です。
def sift_down(heap, i, n):
while True:
smallest = i
l = 2 * i + 1 # left child
r = 2 * i + 2 # right child
if l < n and heap[l] < heap[smallest]:
smallest = l
if r < n and heap[r] < heap[smallest]:
smallest = r
if smallest == i:
break # already in correct position
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap) # valid min-heap again配列からのヒープ構築：Floyd のアルゴリズム
n 個の要素を 1 つずつ単純に挿入すると O(n log n) かかります。Floyd の heapify アルゴリズムは、すべての非葉ノードにシフトダウンを適用することで、O(n) でヒープを構築します。最後の非葉ノード（インデックス n//2 - 1）から開始し、ルートに向かって逆順に処理します。葉ノードはすでに単純なヒープになっているため、内部ノードだけを修正すればよく、全体の処理量は O(n log n) ではなく O(n) になります。
def build_heap(arr):
n = len(arr)
# Start from last non-leaf node: index n//2 - 1
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, i, n)
return arr
arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr) # root should be 1
# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).配列ヒープを使ったヒープソート
ヒープソートは、追加領域 O(1) で O(n log n) で実行されます。フェーズ 1 では、配列から O(n) で max-heap を構築します。フェーズ 2 では、ルートと最後の未ソート要素を交換して最大値を繰り返し取り出し、縮小したヒープに対してシフトダウンを行います。n 回の取り出し後、配列は昇順にソートされています。このインプレースアルゴリズムは、配列表現によって別のデータ構造を確保せずにソートできることを示しています。
def sift_down_max(arr, i, n):
while True:
largest = i
l, r = 2*i+1, 2*i+2
if l < n and arr[l] > arr[largest]: largest = l
if r < n and arr[r] > arr[largest]: largest = r
if largest == i: break
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
def heap_sort(arr):
n = len(arr)
# Build max-heap
for i in range(n // 2 - 1, -1, -1):
sift_down_max(arr, i, n)
# Extract elements one by one
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0] # move max to end
sift_down_max(arr, 0, end)
arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr) # [1, 2, 3, 5, 7, 8, 9]Min-Heap と Max-Heap
min-heap では最小要素がルートにあり、取り出すと常に最小値が得られます。max-heap では最大要素がルートにあり、取り出すと常に最大値が得られます。両者の構造と操作は同じで、比較の向きだけが異なります。Python の heapq モジュールは min-heap のみを実装しているため、max-heap を再現するには値を否定する必要があります。
import heapq
# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap)) # 1
# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
heapq.heappush(max_heap, -val) # negate on push
print('Max-heap max:', -heapq.heappop(max_heap)) # 5 (negate on pop)
# For tuples: heapq sorts by first element
print(min_heap, max_heap)ヒープ操作の計算量まとめ
すべてのヒープ操作は、いずれも O(log n) のシフトアップとシフトダウンから成り立っています。Push：追加 + シフトアップ = O(log n)。Pop：ルートと末尾を交換 + シフトダウン = O(log n)。Peek：インデックス 0 にアクセス = O(1)。ヒープ構築：Floyd のアルゴリズムにより O(n)。ヒープソート：O(n log n)。動的なコレクションから最小値または最大値を繰り返し取得する必要がある場合、この計算量によりヒープが理想的な構造になります。
# Heap complexity summary:
# Operation | Time | Space
# --------------|------------|-------
# Push | O(log n) | O(1)
# Pop (min/max) | O(log n) | O(1)
# Peek | O(1) | O(1)
# Build from n | O(n) | O(1) in-place
# Heap sort | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)
import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data)) # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data)) # [1, 2, 3]面接で使える実践的なヒープパターン
ヒープは、共通のパターンを持つ一連の面接問題を解決します。つまり、n 個の要素をストリームで処理しながら、k 個の候補からなる優先度付きキューを維持します。出現頻度上位 k 個の要素、原点に最も近い k 個の点、タスクスケジューラはいずれもこのパターンを使用します。「n 個の要素のストリームが与えられ、最もよい k 個を維持する」という条件を見たら、このパターンに該当します。常にサイズ k のヒープを使い、全体の計算量は O(n log k) になります。
import heapq
# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
# Use max-heap (negate distance) of size k
heap = []
for x, y in points:
dist = -(x*x + y*y) # negate for max-heap
heapq.heappush(heap, (dist, x, y))
if len(heap) > k:
heapq.heappop(heap) # remove farthest
return [[x, y] for _, x, y in heap]
points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2)) # 2 closest to originヒープとソート済み配列のトレードオフ
最小値または最大値への繰り返しアクセスだけが必要で、コレクションが動的に変化する場合はヒープを選びます。インデックスによるランダムアクセスや範囲検索が必要な場合はソート済み配列を選びます。ヒープの弱点は任意の要素の検索に O(n) かかることです。一方、強みは挿入と削除が O(log n)、最小値と最大値へのアクセスが O(1) であることです。ソート済み配列では挿入に O(n) かかりますが、二分探索による検索は O(log n) です。
# Trade-off comparison:
# Structure | insert | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap | O(logn) | O(logn) | O(n) | O(n)
# Sorted array | O(n) | O(n) | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn) | O(logn)| O(logn+k)
# Hash map | O(1) | O(1) | O(1) | O(n)
# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、ヒープ条件と完全二分木の構造、親と子のインデックス計算式を使った配列表現、そして Floyd の O(n) 構築を含むすべてのヒープ操作の基本要素であるシフトアップとシフトダウンについて学びました。次は heapify を実装し、Python の heapq モジュールを詳しく見ていきます。
よくある質問
「ヒープの性質と配列表現」レッスンは無料ですか？
はい。「ヒープの性質と配列表現」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「ヒープの性質と配列表現」で何を学びますか？
配列に格納された完全二分木の構造を理解し、親子のインデックス計算式を導き、sift-upとsift-down操作を可視化します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「ヒープの性質と配列表現」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。