Written by TY_K
on 

Heap

Heap(ヒップ)

ヒップは、優先順位キューのために作られた資料構造だ。

まず、優先順位キューについて簡単に見てみよう。

優先順位キュー:優先順位の概念をキューに取り入れた資料構造

データが優先順位を持っている。 優先順位の高いデータが先に出る

スタックはLIFO、キューはFIFO

優先順位キューはArray、Linked List、Heapで具現(Heapで具現が最も効率的!)

ヒップ + 挿入:O(logn)、削除:O(logn)

ヒップの種類

最大ヒップ(max heap)

親ノードのキー値が子ノードのキー値より高いか、または同じ完全バイナリツリー

最小ヒップ(minheap)

親ノードのキー値が子ノードのキー値より小さいか、または同じ完全バイナリツリー

heap

実装

ヒップを保存する標準的な資料構造は配列

実装を容易にするために配列の最初のインデックスである0は使用されない。

特定の位置のノード番号は、新しいノードが追加されても変わらない。

(ex. ルートノード(1) の右ノード番号は常に3)

親ノードと子ノードの関係

左の子index = (親index)*2

右の子index = (親index)* 2 + 1

親index = (子index) / 2

ヒップの挿入

1.ヒップに新しい要素が入ってきたら、一旦新しいノードをヒップの最後のノードに挿入

2.新しいノードを親ノードと交換

最大ヒップ挿入を実現

void insert_max_heap(int x) {
    
    maxHeap[++heapSize] = x; 
    // ヒップの大きさを一つ増やし、最後のノードにxを入れる。
    
    for( int i = heapSize; i > 1; i /= 2) {
        
        // 最後のノードが自分の親のノードより大きければ swap
        if(maxHeap[i/2] < maxHeap[i]) {
            swap(i/2, i);
        } else {
            break;
        }
        
    }
}

親ノードは自分のインデックスの/2なので、比較して自分がもっと大きくなったらスプーする方式

ヒップの削除

1.最大ヒップで最大値はルートノードなのでルートノードが削除される(最大ヒップで削除演算は最大値要素を削除すること)

2.削除されたルートノードにはヒップの最後のノードを読み込む

3.”ヒップを再構成”

最大ヒップ削除を実現

int delete_max_heap() {
    
    if(heapSize == 0) // 配列が空いていればリターン
        return 0;
    
    int item = maxHeap[1]; // ルートノードの値を保存
    maxHeap[1] = maxHeap[heapSize]; // 最後のノード値をルートに移動
    maxHeap[heapSize--] = 0; // ヒップの大きさを一つ小さくし、最後のノード0初期化
    
    for(int i = 1; i*2 <= heapSize;) {
        
        // 最後のノードが左ノードと右ノードより大きければ終わり
        if(maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) {
            break;
        }
        
        // 左ノードの方が大きい場合、swap
        else if (maxHeap[i*2] > maxHeap[i*2+1]) {
            swap(i, i*2);
            i = i*2;
        }
        
        // 右ノードの方が大きい場合
        else {
            swap(i, i*2+1);
            i = i*2+1;
        }
    }
    
    return item;
    
}

参照