エンジニア実践的基礎: ヒープ(優先度付きキュー)

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

ヒープ(優先度付きキュー)とは

ヒープ(優先度付きキュー)とは優先度順に値を取り出せる二分木です。最大ヒープと最小ヒープの2種類のヒープが存在します。

最大ヒープは常に最大の値を優先的に取り出します。逆に最小ヒープは常に最小の値を優先的に取り出します。例えば [3, 2, 0, 5] という値が与えられると、最大ヒープなら 5 → 3 → 2 → 0 の順に、最小ヒープなら 0 → 2 → 3 → 5 の順に値を取り出します。最小ヒープも最大ヒープも優先度が逆なだけで、本質は同じなので、以下、最小ヒープについて説明します。

最小ヒープは親ノードが子孫ノードより小さい完全二分木という性質を常に満たす必要があります。親ノードが子孫ノードより小さいという性質は、現在参照しているノードより下にあるノードは全てそのノードより大きいということです。完全二分木とは最下層を除いたすべての階層が完全に埋められており、最下層も左詰めで埋められている

ヒープの性質を満たす

完全二分木ではない

実装

ヒープは今までの実装方法と異なり配列で二分木を表現します。少しトリッキーですが少し考えれば理解できるはずです。次のイメージのヒープを作るとします。

このヒープを配列で表現すると次のようになります。

heap = [None, 10, 15, 16, 20, 24, 18, 50, 55, 33]

第一要素が None になっていることに注目してください。第二要素以降はルートノードから左順に格納されています。なぜ第一要素が None で値が入っていないのかというと、インデックスから親ノード/子ノードを計算するのに都合がいいからです。具体的な例で説明します。

ルートノード 10 のインデックスは 1 です。この左子ノードは 15 でインデックスは 2 です。インデックス 2 はインデックス 1 の2倍です。この法則が全てのノードに当てはまります。ノード 15 の左子ノードのインデックスは 2 × 2 = 4 です。実際に配列のインデックス 4 を確認するとノード 20 が見つかり、ノードの位置と一致します。

次にルートノード 10 の右子ノードのインデックスは 3 です。これはルートノードのインデックス 1 を2倍して 1 を足した数字です。1 × 2 + 1 = 3 この法則も全てのノードに当てはまります。ノード 15 の右子ノードのインデックスは 2 × 2 + 1 = 5 です。実際に配列のインデックス 15 を確認するとノード 24 が見つかり、ノードの位置と一致します。

この二つの法則から、親ノードのインデックスも計算できます。インデックスを 2 で割り、余りを無視するだけです。ノード 15 のインデックスは 2 なので 2 ÷ 2 = 1 で親ノードのインデックスは 1 になります。これはルートノードです。ノード 24 のインデックスは 5 で、5 ÷ 2 = 2 … 1 です。あまりの 1 は無視するので、親ノードのインデックスは 2 です。

ノードに赤字のインデックスを追加したので、色々なノードで親ノード/子ノードのインデックスを計算してください。