[DataStructure] Heap

9142 ワード

Dijkstra

Heapとは?


データの最大値(または最小値)をすばやく検索するデータ構造
優先キューに作成されたデータ構造

<Heapのプロパティ>


  • 完全バイナリツリー

  • 優先度の高いデータはルートにあります

  • 最大お尻と最小お尻
  • 最大HIP:データの最大値がルートディレクトリにある
    ->すべての親ノードが子ノード
  • 以上
  • 最小HIP:データの最小値がルートディレクトリにある
    ->すべての親ノードが子ノード
  • 以下

  • 半整列状態

  • 繰り返し値の許可(バイナリナビゲーションツリーで繰り返し値Xを許可)

  • インプリメンテーション

  • hipを格納標準データ構造は、タイル
  • である.
  • 配列の最初のインデックス0は、
  • の実装を容易にするために使用されない.
  • 特定の場所のノード番号は、新しいノードを追加するときに変更されません.
    (ex.ルートノード(1)の右側ノード番号は常に3)
  • 親ノードと子ノードの関係


    左の子索引=(親索引)2
    右サブインデックス=(親インデックス)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;
            }
            
        }
    }
    親ノードはインデックスの1/2であるため、それらを比較し、より大きい場合に交換します.

    臀部を削除

  • 最大HIPの最大値はルートノードであるため、ルートノード(最大HIPの削除操作は最大値要素の削除である)
  • が削除する.
  • 削除されたルートノードは、最後のヒップホップノード
  • を含む.
  • ヒップホップ
  • を再構成
    <最大臀部削除の実施>
    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;
        
    }