最大値に関する優先度付きキューの実装をc++で学ぶ

最大値を返却する優先度付きキューをc++で実装して見たいと思います。
問題文はALDS1_9_C:Priority Queueを参照してください

実装方法としては、キーが大きいものを優先することから
単純にmaxヒープを使うことで実装できます。
maxヒープに関しては、こちらを参照してください。

まず、キーを挿入するinsert関数からみていきたいと思います。
ヒープのサイズを増やして、正しい位置にキーを挿入する流れになります。

void insert(int key){
    gSize++;
    gHeap[gSize] = -INFINITY;
    increaseKey(gSize, key);
}

increaseKey(int i,int key)関数は
2分ヒープの要素iのkeyを増加させる役割を担います。

void increaseKey(int i ,int key){
    if(key < gHeap[i])return;
    gHeap[i] = key;
    while(i > 1 && gHeap[i / 2] < gHeap[i]){
        swap(gHeap[i],gHeap[i / 2]);
        i = i / 2;
    }
}

キーを交換する箇所では、現在の要素のキーと親の要素のキーを比較して、
要素のキーが大きい間、親の要素との交換を繰り返すことで、正しい位置に挿入します。

例として、{20,9,10,7,6,8,5,1,2,4}に15を追加し、追加した位置にincreaseKye関数を実行して見たいと思います。

           20
      9         10
  7     6    8    5
1 2  4 

           20
      9         10
  7     6    8    5
1 2  4 15

           20
      9         10
  7    15    8    5
1 2  4 6

           20
      15         10
  7    9    8    5
1 2  4 6

優先度付きキュー最大値を取得する

つづいて、最大値を取得するプログラムを書きます。
最大ヒープになっているので、根の値を取得すればいいことになります。
取り出す関数を見ていきます

int extract(){
    int maxv;
    if(gSize < 1) return -INFINITY;
    maxv = gHeap[1];
    gHeap[1] = gHeap[gSize--];
    maxHeapify(1);
    return maxv;
}

一時変数に最大値を保持をさせ、
根にヒープの最後の値を移動し、ヒープのサイズを減らします。
最後に根からmaxHeapify関数を実施します。

例として2分ヒープ{20,9,10,7,6,8,5,1,2,4}から最大値を取り出す様子を図にしてみます。

           20
      9         10
  7     6    8    5
1 2  4 

           4
      9         10
  7     6    8    5
1 2  4 

            4
      9         10
  7     6    8    5
1 2   

           10
      9         8
  7     6    4    5
1 2   

最後にALDS1_9_C:Priority Queue
に対応した全体のソースになります。

#include <iostream>

using namespace std;
#define MAX 2000000
#define INFINITY (1<<30)

int gHeap[MAX + 1],gSize;

void maxHeapify(int i){
    int left,right,largest;
    left = 2 * i;
    right = 2 * i + 1;
    
    // 左の子、自分、右の子で値が最大のノードを選択
    if(left <= gSize && gHeap[left] > gHeap[i]){
        largest = left;
    }
    else{
        largest = i;
    }
    // 右の子と比較
    if(right <= gSize && gHeap[right] > gHeap[largest]) largest = right;
    
    if(largest != i){
        swap(gHeap[i],gHeap[largest]);
        maxHeapify(largest);
    }
}

int extract(){
    int maxv;
    if(gSize < 1) return -INFINITY;
    maxv = gHeap[1];
    gHeap[1] = gHeap[gSize--];
    maxHeapify(1);
    return maxv;
}

void increaseKey(int i ,int key){
    if(key < gHeap[i])return;
    gHeap[i] = key;
    while(i > 1 && gHeap[i / 2] < gHeap[i]){
        swap(gHeap[i],gHeap[i / 2]);
        i = i / 2;
    }
}

void insert(int key){
    gSize++;
    gHeap[gSize] = -INFINITY;
    increaseKey(gSize, key);
}

int main(){
    int key;
    char com[10];
    
    while(1){
        cin >> com;
        if(com[0] == 'e' && com[1] == 'n') break;
        if(com[0] == 'i'){
            cin >> key;
            insert(key);
        }else{
            cout << extract() << endl;
        }
    }
    return 0;
}