DSA Interview Prep · レッスン

heapify、push、popをゼロから実装する

Q: 「heapify、push、popをゼロから実装する」レッスンは無料ですか？

はい。「heapify、push、popをゼロから実装する」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。

Q: DSA Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

Q: 「heapify、push、popをゼロから実装する」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このDSA Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

push用のheapify-upとpop用のheapify-downを実装し、Floydのアルゴリズムで未ソート配列からO(n)でヒープを構築します。

「heapify、push、popをゼロから実装する」はCoddyKit上の無料DSA Interview Prepレッスンです。これはレッスン2/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。

MinHeap クラスの構築

ヒープをゼロから実装すると、その内部の仕組みを理解していることを示せます。また、シニア向けの面接で出題されることもあります。MinHeap クラスは配列をラップし、push、pop、peek、size の操作を公開します。内部では、push 後にシフトアップ、pop 後にシフトダウンを呼び出してヒープ条件を維持します。この実装を理解すると、Python の heapq モジュールの動作を完全に把握できます。

class MinHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

    def pop(self):
        if len(self._data) == 1:
            return self._data.pop()
        min_val = self._data[0]
        self._data[0] = self._data.pop()  # move last to root
        self._sift_down(0)
        return min_val

    def peek(self):
        return self._data[0] if self._data else None

    def size(self):
        return len(self._data)

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

print('MinHeap class skeleton defined')

シフトアップの実装

シフトアップでは、ヒープ条件（min-heap では parent <= child）が破られている間、ノードとその親を比較して上方向に交換します。重要なのは、新しく挿入された要素が末尾にあり、正しい位置まで上に移動することです。while ループは木の高さである floor(log n) 回までしか実行されません。各ステップで i = parent を代入し、上方向への移動を続けます。

class MinHeap:
    def __init__(self):
        self._data = []

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

    def _sift_up(self, i):
        while i > 0:
            p = self._parent(i)
            if self._data[p] > self._data[i]:  # parent > child: swap
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else:
                break  # heap property satisfied

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

h = MinHeap()
for v in [5, 3, 8, 1, 4]:
    h.push(v)
print(h._data)  # valid min-heap

シフトダウンの実装

シフトダウンでは、ノードを最小の子（min-heap の場合）と繰り返し交換して下方向に移動させます。どちらの子も小さくない状態になるか、ノードが葉に到達するまで続けます。ヒープ条件を維持するため、必ず両方の子と比較し、小さい方と交換してください。値を比較する前に、子のインデックスが範囲内にあることを確認してください。

def _sift_down(data, i):
    n = len(data)
    while True:
        smallest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and data[l] < data[smallest]:
            smallest = l
        if r < n and data[r] < data[smallest]:
            smallest = r
        if smallest == i:
            break  # already the smallest among i, l, r
        data[i], data[smallest] = data[smallest], data[i]
        i = smallest

# Test: put a large value at root and sift down
heap = [10, 1, 2, 3, 4, 5, 6]
print('Before sift-down:', heap)
_sift_down(heap, 0)
print('After sift-down:', heap)  # 1 should reach top, 10 sink

MinHeap に Pop を実装する

pop 操作はルート（min-heap では最小値）を削除して返します。完全二分木の形状を維持するため、最後の要素をルート位置に移動してからシフトダウンします。これにより配列内に空きが生じず、配列表現を有効な状態に保てます。エッジケースとして、要素が 1 つだけ残っている場合は、シフトダウンせずに直接取り出して返します。

class MinHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        i = len(self._data) - 1
        while i > 0:
            p = (i - 1) // 2
            if self._data[p] > self._data[i]:
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else: break

    def pop(self):
        if not self._data: return None
        if len(self._data) == 1: return self._data.pop()
        result = self._data[0]
        self._data[0] = self._data.pop()  # last -> root
        i, n = 0, len(self._data)
        while True:
            s, l, r = i, 2*i+1, 2*i+2
            if l < n and self._data[l] < self._data[s]: s = l
            if r < n and self._data[r] < self._data[s]: s = r
            if s == i: break
            self._data[i], self._data[s] = self._data[s], self._data[i]
            i = s
        return result

h = MinHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)])  # [1,2,3,4,5,8] sorted

Floyd の Heapify アルゴリズム

Floyd のアルゴリズムは、ソートされていない配列のすべての非葉ノードにシフトダウンを適用することで、O(n) で min-heap を構築します。最後の内部ノード（n//2 - 1）から始めて、ルートに向かって処理します。葉は 1 要素のヒープとしてすでに自明に有効です。ほとんどのノードは木の下部にあり、短い距離だけシフトダウンすればよいため、O(n) の計算量が実現します。

def heapify(arr):
    n = len(arr)
    # Start from last non-leaf: index n//2 - 1
    # Work backward to root (index 0)
    for i in range(n // 2 - 1, -1, -1):
        # Sift down node at index i
        j = i
        while True:
            s = j
            l, r = 2*j+1, 2*j+2
            if l < n and arr[l] < arr[s]: s = l
            if r < n and arr[r] < arr[s]: s = r
            if s == j: break
            arr[j], arr[s] = arr[s], arr[j]
            j = s
    return arr

arr = [9, 7, 5, 3, 1, 8, 2, 4, 6]
print('Before:', arr)
heapify(arr)
print('After (min-heap):', arr)  # arr[0] should be 1

Floyd のアルゴリズムが O(n) である理由

O(n) の証明は次のとおりです。木には高さ k のノードが n/2^(k+1) 個あります。高さ k の各ノードは、シフトダウン中に最大 k 回交換します。全体の処理量は、すべての高さ k についての n/2^(k+1) * k の合計です。この等比級数は O(n) に収束します。一方、単純に 1 つずつ挿入する場合、各 push は O(log n) なので、n 回の push には O(n log n) かかります。Floyd のアルゴリズムは、バッチ構築では厳密に優れています。

import time
import random

# Compare: O(n) heapify vs O(n log n) one-by-one
n = 100000
data = list(range(n, 0, -1))  # reverse sorted = worst case for push

# Method 1: Floyd's O(n)
data1 = data[:]
start = time.time()
for i in range(n // 2 - 1, -1, -1):
    j = i
    while True:
        s = j; l, r = 2*j+1, 2*j+2
        if l < n and data1[l] < data1[s]: s = l
        if r < n and data1[r] < data1[s]: s = r
        if s == j: break
        data1[j], data1[s] = data1[s], data1[j]; j = s
print(f'Floyd heapify: {time.time()-start:.4f}s')

# Method 2: One-by-one insertion
import heapq
start = time.time()
heap = []
for x in data: heapq.heappush(heap, x)
print(f'Push one-by-one: {time.time()-start:.4f}s')

既存コレクションへのヒープ Push

Python の heapq.heappushpop と heapq.heapreplace は、複数の処理を組み合わせた効率的な操作です。heappushpop(heap, item) は新しい要素を追加して、直後に最小値を取り出します。2 回の別々の呼び出しより効率的です。heapreplace(heap, item) は最小値を取り出して新しい要素を 1 回の処理で追加します（正しく動作させるには、新しい要素が以前の最小値以上である必要があります）。これらは上位 k 個を求めるストリーミングアルゴリズムで役立ちます。

import heapq

heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)

# heappushpop: push 2, then pop minimum
# More efficient than push + pop separately
result = heapq.heappushpop(heap, 2)
print('heappushpop(2):', result, '| heap:', heap)

# heapreplace: pop minimum, then push new item
# New item does NOT need to be larger (different from heappushpop)
result2 = heapq.heapreplace(heap, 4)
print('heapreplace(4):', result2, '| heap:', heap)

# Use case: maintaining a fixed-size top-k heap
# heappushpop is the standard pattern

MaxHeap をゼロから実装する

MaxHeapでは比較の向きが反転し、親はすべての子孫以上でなければなりません。シフトアップとシフトダウンの比較を反転するだけで実装できます。別の方法として、値を否定するクラスでラップするか、Python の heapq で行うように整数を否定します。ゼロから実装すると、min-heap と max-heap は比較演算子だけが異なる同一の構造であることが分かります。

class MaxHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        i = len(self._data) - 1
        while i > 0:
            p = (i - 1) // 2
            if self._data[p] < self._data[i]:  # FLIP: parent < child = violation
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else: break

    def pop(self):
        if not self._data: return None
        if len(self._data) == 1: return self._data.pop()
        result = self._data[0]
        self._data[0] = self._data.pop()
        i, n = 0, len(self._data)
        while True:
            g = i; l, r = 2*i+1, 2*i+2
            if l < n and self._data[l] > self._data[g]: g = l  # FLIP
            if r < n and self._data[r] > self._data[g]: g = r  # FLIP
            if g == i: break
            self._data[i], self._data[g] = self._data[g], self._data[i]; i = g
        return result

h = MaxHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)])  # [8,5,4,3,2,1]

ヒープから任意の要素を削除する

任意の要素（ルート以外）をヒープから削除する操作は O(log n) ですが、その要素のインデックスを知っている必要があります。その要素を最後の要素で置き換え、最後の要素を削除してから、置き換えた要素にシフトアップまたはシフトダウンを行います。ヒープ条件に違反する方向は一方だけです。この手法は、遅延削除を使う Dijkstra のアルゴリズムや、decrease-key 操作をサポートする優先度付きキューで使用されます。

def delete_at_index(heap, i):
    n = len(heap)
    heap[i] = heap[n - 1]
    heap.pop()
    if i >= len(heap):
        return  # deleted the last element
    # Try sift-up first
    p = (i - 1) // 2
    if i > 0 and heap[i] < heap[p]:
        while i > 0:
            p = (i - 1) // 2
            if heap[p] > heap[i]:
                heap[p], heap[i] = heap[i], heap[p]; i = p
            else: break
    else:  # sift down
        j = i; n2 = len(heap)
        while True:
            s = j; l, r = 2*j+1, 2*j+2
            if l < n2 and heap[l] < heap[s]: s = l
            if r < n2 and heap[r] < heap[s]: s = r
            if s == j: break
            heap[j], heap[s] = heap[s], heap[j]; j = s

heap = [1, 3, 2, 7, 4, 5, 6]
print('Before:', heap)
delete_at_index(heap, 2)  # delete element at index 2 (value=2)
print('After:', heap)  # 2 removed, heap still valid

Top-K 頻出要素におけるヒープ

Top-K Frequent Elements（LeetCode #347）では、サイズ k の min-heap を使用します。各エントリが (frequency, element) である min-heap を維持します。各一意な要素を処理し、ヒープの要素数が k 未満なら追加します。それ以外の場合は、新しい要素の頻度がヒープ内の最小値を超えていれば、最小値を取り出して新しい要素を追加します。最終的なヒープには、O(n log k) 時間で出現頻度の最も高い k 個の要素が含まれます。

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)
    # Min-heap of (frequency, num)
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)  # remove least frequent
    return [num for freq, num in heap]

print(top_k_frequent([1,1,1,2,2,3], 2))  # [1, 2]
print(top_k_frequent([4,4,4,3,3,2,1], 2)) # [4, 3]

スケジューリングにおけるヒープの応用

競技プログラミングにとどまらず、ヒープは実際のスケジューリングシステムを支えています。オペレーティングシステムのタスクスケジューラは、優先度付きキュー（ヒープ）を使って、実行可能なプロセスの中から最も優先度の高いものを常に実行します。イベント駆動シミュレーションでは、イベント時刻をキーとする最小ヒープを使い、時刻順にイベントを処理します。ネットワークパケットスケジューラは、サービス品質（QoS）クラスに基づいてトラフィックの優先順位を付けます。ヒープを理解することで、これらすべてのシステムに対するメンタルモデルを持てるようになり、キューイングやスケジューリングに関するシステム設計面接でも自然に役立ちます。

import heapq

# Simple event-driven simulation using a heap
events = []  # (time, event_description)

def schedule(time, event):
    heapq.heappush(events, (time, event))

def process_next():
    time, event = heapq.heappop(events)
    print(f't={time}: {event}')
    return time, event

# Schedule events out of order:
schedule(10, 'Send email')
schedule(3,  'Open app')
schedule(7,  'Process request')
schedule(1,  'Start server')

# Process in time order:
while events:
    process_next()
# Output: t=1, t=3, t=7, t=10 -- always in time order

理解度チェック

このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、MinHeapとMaxHeapをゼロから実装する方法としてシフトアップとシフトダウン、FloydのO(n)ヒープ構築アルゴリズムと、1つずつ挿入するO(n log n)より高速である理由、さらにトップk頻出要素やインデックスを指定した削除などの実践的な応用を学びました。次はPythonのheapqモジュールと、最大ヒープを実現するテクニックを扱います。

よくある質問