データ構造の学習でヒープ構造を学ぶ際に「理論はわかったけど、実際の実装はどうするの？」と疑問を感じる方も多いのではないでしょうか。
この記事では、ヒープ構造のデータ構造としての実装方法と主要な操作について、挿入・削除・ヒープ化・上向き調整・下向き調整・配列での実装まで詳しく解説しています。
ヒープの実装を理解することで、アルゴリズムの理解がより深まるでしょう。
ヒープ構造の実装方法と配列表現の基礎
それではまず、ヒープ構造の実装方法と配列表現の基礎について解説していきます。
ヒープ構造は完全二分木の性質を利用して、ポインタを使わずに配列（1次元のリスト）だけで効率よく実装できます。
配列のインデックスと木の親子関係を数式で対応させることで、追加メモリなしにヒープを実現できます。
配列によるヒープ実装の基本コード
Pythonでの最大ヒープの基本クラス実装：
class MaxHeap:
def __init__(self):
self.heap = []
def parent(self, i): return (i – 1) // 2
def left_child(self, i): return 2 * i + 1
def right_child(self, i): return 2 * i + 2
def size(self): return len(self.heap)
def get_max(self): return self.heap[0] if self.heap else None
ヒープ構造の各操作の概要
| 操作 | 英語名 | 計算量 | 概要 |
|---|---|---|---|
| 挿入 | Insert / Push | O(log n) | 末尾に追加して上向き調整 |
| 最大値取り出し | Extract Max / Pop | O(log n) | 根を削除して下向き調整 |
| ヒープ化 | Heapify | O(n) | 配列全体をヒープに変換 |
| 最大値参照 | Peek | O(1) | 根を見るだけ（削除なし） |
挿入操作と上向き調整の実装
続いては、挿入操作と上向き調整の実装を確認していきます。
挿入操作（Insert）の手順と実装
ヒープへの要素の挿入は「末尾に追加してから上向き調整（Sift Up）」という2ステップで行います。
挿入と上向き調整のPython実装：
def insert(self, value):
self.heap.append(value) # 末尾に追加
self._sift_up(len(self.heap) – 1) # 上向き調整
def _sift_up(self, i):
while i > 0 and self.heap[self.parent(i)] < self.heap[i]:
# 親より大きければ交換（最大ヒープ条件）
p = self.parent(i)
self.heap[i], self.heap[p] = self.heap[p], self.heap[i]
i = p
上向き調整は親ノードとの比較・交換を繰り返し、木の根に近づく方向に要素を移動させるため、最大でも木の高さO(log n)回の操作で完了します。
削除操作と下向き調整の実装
続いては、削除操作と下向き調整の実装を確認していきます。
最大値取り出し操作（Extract Max）の実装
削除と下向き調整のPython実装：
def extract_max(self):
if not self.heap: return None
max_val = self.heap[0]
self.heap[0] = self.heap[-1] # 末尾を根に移動
self.heap.pop() # 末尾を削除
if self.heap:
self._sift_down(0) # 根から下向き調整
return max_val
def _sift_down(self, i):
n = len(self.heap)
largest = i
l, r = self.left_child(i), self.right_child(i)
if l < n and self.heap[l] > self.heap[largest]: largest = l
if r < n and self.heap[r] > self.heap[largest]: largest = r
if largest != i:
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
self._sift_down(largest)
ヒープ化（Build Heap）の実装
既存の配列を最大ヒープに変換する「ヒープ化（Build Heap）」は、最後の内部ノード（インデックス(n//2)-1）から根に向かって順に下向き調整を適用することでO(n)で実現できます。
1要素ずつ挿入するO(n log n)の方法よりも、このヒープ化はO(n)の計算量で完了するためヒープソートなどで重要な最適化となっています。
まとめ
この記事では、ヒープ構造のデータ構造としての実装方法と主要な操作について、挿入・削除・ヒープ化・上向き下向き調整の実装コードとともに詳しく解説しました。
ヒープ構造は配列1本で完全二分木を表現し、O(log n)の効率的な挿入・削除とO(1)の最大値参照を実現する非常に実用的なデータ構造です。
今回の実装例を参考に、ヒープ構造をコードで実際に書いて理解を深めてみてください。
