C++で最小ヒープから値x未満のすべてのノードを出力する方法

この問題では、最小ヒープ(Min Heap)と値xが与えられ、xより小さい値を持つすべてのノードを出力することが求められます。

最小ヒープとは、すべての親ノードがその子ノードの値以下となる特殊な二分木です。この性質により、根(ルート)には常にヒープ内の最小値が格納されます。

具体例を使って問題を理解しましょう。

X = 45

出力 − 2 4 7 10 17 22 33 34

この問題を解くには、最小ヒープ全体を先行順トラバーサル(前順走査)で探索し、与えられた値xより小さい値を持つノードのみを出力します。

アルゴリズムのポイント

最小ヒープでは親ノードの値が必ず子ノード以下であるため、あるノードの値がx以上であった場合、その子孫ノードの値も必ずx以上になります。そこで、条件を満たさないノードに到達した時点でその部分木の探索を打ち切る(枝刈りを行う)ことで、無駄な探索を省き、効率的に処理できます。トラバーサルには再帰を利用します。

実装例

ソリューションの動作を示すプログラム

#include <iostream>
using namespace std;
class MinHeap {
    int* harr;
    int capacity;
    int heap_size;
    public:
    MinHeap(int capacity);
    void Heapify(int);
    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return (2 * i + 1); }
    int right(int i) { return (2 * i + 2); }
    void insert(int k);
    void printSmallerNodes(int k, int pos);
};
void MinHeap::printSmallerNodes(int x, int pos = 0){
    if (pos >= heap_size)
        return;
    if (harr[pos] >= x) {
        return;
    }
    cout<<harr[pos]<<" ";
    printSmallerNodes(x, left(pos));
    printSmallerNodes(x, right(pos));
}
MinHeap::MinHeap(int cap) {
    heap_size = 0;
    capacity = cap;
    harr = new int[cap];
}
void MinHeap::insert(int k) {
    if (heap_size == capacity) {
        cout << "\nオーバーフロー! サイズが満杯です\n";
        return;
    }
    heap_size++;
    int i = heap_size - 1;
    harr[i] = k;
    while (i != 0 && harr[parent(i)] > harr[i]) {
        swap(harr[i], harr[parent(i)]);
        i = parent(i);
    }
}
void MinHeap::Heapify(int i) {
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l] < harr[i])
        smallest = l;
    if (r < heap_size && harr[r] < harr[smallest])
        smallest = r;
    if (smallest != i) {
        swap(harr[i], harr[smallest]);
        Heapify(smallest);
    }
}
int main() {
    MinHeap h(50);
    h.insert(2);
    h.insert(4);
    h.insert(7);
    h.insert(34);
    h.insert(52);
    h.insert(33);
    h.insert(10);
    h.insert(51);
    h.insert(75);
    h.insert(17);
    h.insert(22);
    int x = 45;
    cout<<"値が "<<x<<" より小さいすべてのノードは\n";
    h.printSmallerNodes(x);
    return 0;
}

出力

値が 45 より小さいすべてのノードは 2 4 34 17 22 7 33 10

このプログラムでは、まず各値をinsert関数でヒープに挿入し、ヒープ性質を維持しながら構築しています。その後、printSmallerNodes関数が根から再帰的に先行順で木を走査し、x未満の値を出力します。計算量は、枝刈りにより出力対象のノード数に比例して抑えられ、最悪の場合でもヒープ全体でO(n)です。