C++でヒープソートを実装する方法：最小ヒープの完全ガイド

ヒープとは

ヒープ（Heap）とは、完全二分木のデータ構造であり、「最小ヒープ（Min Heap）」または「最大ヒープ（Max Heap）」のいずれかに分類されます。

最大ヒープでは、ルートノードのキーがヒープ内のすべてのキーの中で最大値である必要があり、この性質は木の中のすべてのノードに対して再帰的に成り立たなければなりません。最小ヒープはその逆で、親ノードの値が常に子ノードの値以下になるという性質を持ちます。本記事では、最小ヒープを用いたヒープソートの実装方法を解説します。

実装する関数の概要

今回実装するクラスには、以下の主要なメンバ関数が含まれています。

• void BHeap::Insert(int ele)：ヒープに要素を挿入する操作を行います。
• void BHeap::DeleteMin()：ヒープから最小値を削除する操作を行います。
• int BHeap::ExtractMin()：ヒープから最小値を取り出す（参照する）操作を行います。
• void BHeap::showHeap()：ヒープ内の要素をすべて表示します。
• void BHeap::heapifyup(int in)：ボトムアップ方式でヒープ構造を維持します。
• void BHeap::heapifydown(int in)：トップダウン方式でヒープ構造を維持します。

C++によるサンプルコード

以下は、vector を内部データ構造として使用し、メニュー形式でヒープ操作を試せる完全なサンプルプログラムです。

#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
class BHeap {
    private:
        vector <int> heap;
        int l(int parent);
        int r(int parent);
        int par(int child);
        void heapifyup(int in);
        void heapifydown(int in);
    public:
        BHeap()
        {}
        void Insert(int element);
        void DeleteMin();
        int ExtractMin();
        void showHeap();
        int Size();
};
int main() {
    BHeap h;
    while (1) {
        cout<<"1.Insert Element"<<endl;
        cout<<"2.Delete Minimum Element"<<endl;
        cout<<"3.Extract Minimum Element"<<endl;
        cout<<"4.Show Heap"<<endl;
        cout<<"5.Exit"<<endl;
        int c, e;
        cout<<"Enter your choice: ";
        cin>>c;
        switch(c) {
            case 1:
                cout<<"Enter the element to be inserted: ";
                cin>>e;
                h.Insert(e);
                break;
            case 2:
                h.DeleteMin();
                break;
            case 3:
                if (h.ExtractMin() == -1) {
                    cout<<"Heap is Empty"<<endl;
                }
                else
                    cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
                break;
            case 4:
                cout<<"Displaying elements of Heap: ";
                h.showHeap();
                break;
            case 5:
                exit(1);
            default:
                cout<<"Enter Correct Choice"<<endl;
        }
    }
    return 0;
}
int BHeap::Size() // ヒープのサイズを返す {
    return heap.size();
}
void BHeap::Insert(int ele) // ヒープに要素を挿入 {
    heap.push_back(ele);// 要素をヒープの末尾に追加
    heapifyup(heap.size() -1);// heapifyup()を呼び出してヒープ構造を維持
}
void BHeap::DeleteMin() // ヒープから最小値を削除 {
    if (heap.size() == 0) {
        cout<<"Heap is Empty"<<endl;
        return;
    }
    heap[0] = heap.at(heap.size() - 1);
    heap.pop_back();// 末尾の要素を削除
    heapifydown(0);
    cout<<"Element Deleted"<<endl;
}
int BHeap::ExtractMin() // ヒープから最小値を取り出す
{
    if (heap.size() == 0) {
        return -1;
    }
    else
        return heap.front();
}
void BHeap::showHeap() // ヒープの要素を表示 {
    vector <int>::iterator pos = heap.begin();
    cout<<"Heap --> ";
    while (pos != heap.end()) {
        cout<<*pos<<" ";
        pos++;
    }
    cout<<endl;
}
int BHeap::l(int parent) // ノードの左の子を返す。
{
    int l = 2 * parent + 1;
    if (l < heap.size())
        return l;
    else
        return -1;
}
int BHeap::r(int parent) // ノードの右の子を返す。
{
    int r = 2 * parent + 2;
    if (r < heap.size())
        return r;
    else
        return -1;
}
int BHeap::par(int child)// 親ノードを返す
{
    int p = (child - 1)/2;
    if (child == 0)
        return -1;
    else
        return p;
}
void BHeap::heapifyup(int in)// ボトムアップ方式でヒープ構造を維持する。
{
    if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in]) {
        int temp = heap[in];
        heap[in] = heap[par(in)];
        heap[par(in)] = temp;
        heapifyup(par(in));
    }
}
void BHeap::heapifydown(int in)// トップダウン方式でヒープ構造を維持する。
{
    int child = l(in);
    int child1 = r(in);
    if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) {
        child = child1;
    }
    if (child > 0 && heap[in] > heap[child]) {
        int t = heap[in];
        heap[in] = heap[child];
        heap[child] = t;
        heapifydown(child);
    }
}

実行結果

上記プログラムをコンパイルして実行すると、以下のように対話形式でヒープ操作を確認できます。要素「2」「3」「7」「6」を挿入した後、最小値の取得・削除を行った例です。

1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 2
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 3
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 7
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 6
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 4
Displaying elements of Heap: Heap --> 2 3 7 6
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 3
Minimum Element: 2
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 3
Minimum Element: 2
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 2
Element Deleted
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 4
Displaying elements of Heap: Heap --> 3 6 7
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 5

まとめ

このように、C++の vector を使えば、配列ベースのバイナリヒープをシンプルに実装できます。挿入時は heapifyup() で親と比較しながら上方へ移動させ、削除時は最後の要素を根に移動して heapifydown() で下方へ調整することで、常にヒープの性質（親 ≤ 子）が保たれます。ヒープソートや優先度付きキューの基礎として、ぜひ理解を深めてください。