コンテナアダプタに関する記事C++プログラマへの道 #12 - コンテナアダプタでは、 ヒープデータ構造の概念について簡単に触れました。さまざまなツリー構造について学んだ今、優先度付きキューを実装するために使用されるヒープについて詳しく説明します。 (データ構造としてのヒープは、ヒープメモリ領域とは関係ありません。)

ヒープ

シンプルな二分探索木 (BST) では、左部分木のノードは常に小さく、右部分木のノードは常に親ノードよりも大きくなければならないという制約があります。 これにより、探索時に比較によって候補ノードを絞り込むことができます。しかし、場合によっては優先度付きキューのように、最小または最大の要素だけを見つけたいこともあります。 そういった場合には、最小または最大ヒープを使用することで、最小または最大の要素を $O(1)$ 時間で取得することができます。

二分木をヒープにするためには、二分木が次の2つのルールを満たす必要があります。まず、親ノードは最小ヒープでは子ノード（左・右）よりも小さく、 最大ヒープでは子ノードよりも大きくなければなりません。これにより、ルートノードが最小または最大の要素となります。 次に、新しい要素を挿入するときは、最下層のすべてのノードが左から順に埋まっている必要があります。これにより、ツリーがバランスを保つことができます。

#include <vector>
using namespace std;
 
class MinHeap {
    public:
        int size;
        int capacity;
        vector<int> heap;
 
        int parent(int i) {return (i - 1) / 2;};
        int left(int i) {return 2 * i + 1;};
        int right(int i) {return 2 * i + 2;};
 
    MinHeap(int capacity): capacity(capacity) {
        size = 0;
        heap.resize(capacity);
    };
};

上記は最小ヒープのコードです。ヒープでは、個別のノードを使うのではなく、ベクトルを使うのが一般的です。 これにより、最小または最大の要素に迅速にアクセスできます。技術的にはベクトルでBSTを実装することも可能ですが、 ヒープでは同じ高さのノードの大小が固定されていないため、ベクトルを使って効率的に左から順にノードを追加することができます。 parent、left、right メソッドは、ツリーが最下層以外は完全に埋まっていることを前提とし、親、左子、右子ノードのインデックスを返します。

挿入

ヒープに要素を挿入する際、ヒープの容量がすでにいっぱいのケースと、新しい要素がヒープの特性を破るケースを考慮する必要があります。 前者の場合、単にヒープをリサイズします。後者の場合、挿入された要素を親ノードと入れ替えて、正しい位置に収まるまで繰り返します。 以下に最小ヒープの挿入の実装を示します。

void MinHeap::insert(int n) {
    // Case 1: size
    if (size == capacity) {
        cout << "Heap is full. Please allocate more memory. " << endl;
        return;
    }
 
    // Inserting at the end
    int ind = size - 1;
    heap[ind] = n;
    size++;
 
    // Case 2: swapping
    while (ind != 0  && heap[parent(ind)] > heap[ind]) {
        swap(heap[ind], heap[parent(ind)]); // swap from std
        ind = parent(i);
    }
};

ご覧の通り、ヒープにおける挿入は比較的簡単です。while ループがルートまで遡る可能性があるため、挿入の時間計算量はヒープの高さに比例し、$O(\log(n))$ となります。

削除

ヒープでの削除は、優先度付きキューのようにルートノードを取り出す操作を指すことが多いです。 ルートを削除するときは、ツリーの形を維持するためにヒープの最後の要素を一時的にルートに置き換えますが、 これによってヒープの特性が破られる可能性があるため、heapify 関数を使って修正します（詳しくは後述します）。 以下はルートノードを削除する extractMin 関数です。

int MinHeap::extractMin() {
    if (size == 0) {
        cout << "This Heap is currently empty." << endl;
        return -1;
    }
 
    if (size == 1) {
        size--;
        return heap[0];
    }
 
    int root = heap[0];
    heap[0] = heap[size - 1];
    size--;
    heapify(0); // heapify method
    
    return root;
};

ヒープの要素数が0の場合、エラーメッセージを表示して -1 を返します。要素が1つだけの場合、サイズを修正してルートを返します。 それ以外の場合、ルートを最後の要素で置き換え、heapify メソッドを実行してヒープ特性を復元します。heapify 関数の実装を以下に示します。

void MiniHeap::heapify(int i) {
    int l = left(i);
    int r = right(i);
    int smallest = i;
 
    // Identify the smallest among i, left and right children
    if (l < size && heap[l] < heap[smallest]) {
        smallest = l;
    }
    if (r < size && heap[r] < heap[smallest]) {
        smallest = r;
    }
 
    // If the smallest is not i, then we need to swap it with smallest and continue heapifing
    if (smallest != i) {
        swap(heap[i], heap[smallest]);
        heapify(smallest);
    }
};

heapify 関数は、入力ノードとその子ノードを比較し、必要に応じて最小のノードと交換することで、ヒープの特性を保持します。 入力ノードが最小である場合、ヒープの特性が満たされていますが、そうでない場合は再帰的に適用して違反を解消します。 heapify は最大でツリーの高さ分だけノードを処理する必要があるため、heapify と extractMin の時間計算量は $O(\log(n))$ となります。

配列からヒープへの変換

場合によっては、追加のメモリを使用せずに既存の配列から直接ヒープを作成したいことがあります。 この場合、葉ノード以外のノードに対して逆順にヒープ化(heapify)することで対応可能です。

void MinHeap::fromArray(int arr[], int arr_size) {
    if (arr_size > capacity) {
        cout << "Size is bigger than the capacity." << endl;
        return;
    }
    size = arr_size;
    copy(arr, arr + arr_size, heap.begin()); // copy from std
 
    int lst = parent(arr_size); // last non-leaf node
    for (int i = lst; i >= 0; i--) {
        heapify(i);
    }
};

上記は、配列からヒープを構築するコード実装です。fromArray 関数は標準ライブラリの copy 関数を使用して配列の内容をヒープにコピーし、 葉ノード以外のノードを逆順にヒープ化(heapify)します。このメソッドは非葉ノードを反復処理するため、時間計算量は配列のサイズに比例して$O(n)$ です。

ヒープソート

ヒープの持つ、最小値または最大値に$O(1)$でアクセスできる特性は、優先度付きキューの実装だけでなく、効率的な配列のソートにも役立ちます。 記事Cプログラマへの道 #12 - ソートアルゴリズムでは、いくつかのソートアルゴリズムとその計算量を紹介し、 その中には選択ソートも含まれていました。選択ソートは、右側のサブ配列から最小の要素を選び出し、左側のサブ配列に追加していくアルゴリズムです。 選択ソートは$n$回の反復ごとに線形探索が必要であるため、計算量は$O(n^2)$になります。

線形探索の代わりに、配列を最小ヒープに変換して（fromArrayメソッドを使用）、最小ヒープを利用して右側のサブ配列から最小要素を繰り返し取り出す（extractMinメソッドを使用）ことで、 $O(\log(n))$の時間で処理が可能です。この手法はヒープソートと呼ばれ、計算量は$O(n \log(n))$になります。ヒープソートの計算量はクイックソートと同等で、比較的効率的です。

結論

ヒープは、挿入と削除で$O(\log(n))$の計算量、最小または最大値へのアクセスで$O(1)$の計算量を達成し、比較的シンプルなルールにより、優先度付きキューやヒープソートといった用途に適しています。挑戦として、ぜひ自分で最大ヒープを実装してみてください。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

リソース

• CoffeeBeforeArch. 2019. C++ Data Structures: Min-Heaps. YouTube.
• Inside code. 2021. Heaps, heapsort, and priority queues - Inside code. YouTube.