[C] Indexed Priority Queue (Indexed Heap)


インデックス優先キューYes


heapの特定の値のheapデータ構造を変更できます.
[]という配列を指定し、heap[]に変換します.heap[]のa[i]値を直ちに変更し、heapのデータ構造を保持できます.

時間の複雑さ


仮にa[0]、a[1]...a[n−1]が存在する場合に以下のクエリのコードを実装してみる.
  • update(i, v)a[i]=v.
  • get_min()a[0]~a[n-1]中出力最小値
  • この機能を単純heapで実現すると、更新のたびにnを押して配列をブラウズしてa[i]を修正し、配列全体にheapifyを行うとO(N)+O(N)となる.
    ただし、インデックスheapでは特定の配列値のみが変更されます&heap構造が保持されている場合はO(1)+O(logn)です.

    さぎょうモード

    1. a[i]에 해당하는 값이 Heap상에서 어디에 위치하는지를 O(1)만에 알아내고
    2. 그 노드의 값을 v로 바꿔버리고
    3. Heap 자료구조를 유지시키도록 노드를 O(log n)만에  옮긴다.
    heap index[]配列を計算し、swapのたびに更新することが重要です.
    iが与えられた場合、heap[]からa[i]を格納するインデックスを取得する->直接通過heap_index[i].
    heap index[i]のa[i]のheapのインデックスを更新し続ける必要があります.
    したがって、heap[heap_index[i]]現在のheapにおけるa[i]ノードの位置.
    void heap_update_direct(int i, int v)
    {
      heap[heap_index[i]].val = v;
     ... 중략
    }
    heap index[i]は、a[i]が現在heap内にある位置を決定することができる.これはpush/pop時に保存とメンテナンスが必要です.
    まず,heapデータ構造を次のように仮定する.
    struct elem {
        int idx;
        int val;
    };
    struct pq {
        int heap_size;
        struct elem *heap;
    };
    struct pq *q;
    heap_index[];       // <-

    heap_push


    a[i]を押すと、ノードはheapの最後に格納されます.したがって、heapに格納されているa[i]のインデックスは、現在のheapサイズになります.
    heap index[「ノードをプッシュするidx」=q->heap size;
    void heap_push(struct elem heap[], int val, int idx)
    {
        heap[q->heap_size].val = val;
        heap[q->heap_size].idx = idx;
        heap_index[idx] = q->heap_size;      // <-
        q->heap_size++;
        heapify_up(heap, q->heap_size - 1);
    }
    次に、親モードと交換されるheapify up()を実行し、heap index[]を毎回同時に更新する必要があります.
    void heapify_up(struct elem heap[], int curr_idx)
    {
        int p_idx = (curr_idx - 1) / 2;
        
        if (curr_idx < 1)
            return;
        if (heap[curr_idx].val < heap[p_idx].val) {
            swap(heap, curr_idx, p_idx);
            heap_index[heap[curr_idx].idx] = curr_idx;   // <-
            heap_index[heap[p_idx].idx] = p_idx;         // <-
            heapify_up(heap, p_idx);
        }
    }
            swap(heap, curr_idx, p_idx);
            heap_index[heap[curr_idx].idx] = curr_idx;   // <-
            heap_index[heap[p_idx].idx] = p_idx;         // <-
    swapの後、heap[curr_idx].idxはp idxに置き換えられるので、既存のa[p idx]はheapのどのidxに存在するか、すなわちheap index[p idx]はcurr idxでswapを行わなければならない.
    heap[curr idx]をheap[p idx]と交換すると、heap[curr idx]はp idxに対応するstruct elem要素を格納します.したがって、curr idxを使用して、既存のp idxに対応するheap index[]を更新する必要があります.したがってheap index[]配列もswapとなる.

    heap_pop


    popはheap index[]を0に変更します.heapの最後の要素が[0]に上昇するからです.
    heapify downの場合、heap indexを交換することでheap indexを更新することもできます.
    struct elem heap_pop(struct elem arr[], bool (*cmp)(struct elem, struct elem))
    {
        struct elem ret = arr[0];
        swap(arr, 0, q->heap_size -1);
        q->heap_size--;
        heap_index[arr[0].idx] = 0;    //  <-
        heapify_down(arr, 0, q->heap_size, cmp);
        return ret;
    }
    void heapify_down(struct elem arr[], int p_idx, int size, bool (*cmp)(struct elem, struct elem))
    {
        int min_idx = p_idx;
        int l_idx = p_idx * 2 + 1;
        int r_idx = p_idx * 2 + 2;
        
        if (l_idx < size && cmp(arr[l_idx], arr[min_idx]))
            min_idx = l_idx;
        if (r_idx < size && cmp(arr[r_idx], arr[min_idx]))
            min_idx = r_idx;
        if (min_idx != p_idx) {
            swap(arr, min_idx, p_idx);
            heap_index[heap[min_idx].idx] = min_idx;   // <-
            heap_index[heap[p_idx].idx] = p_idx;         // <-
            heapify_down(arr, min_idx, size, cmp);
        }
    }

    heap_update_direct


    最後に、以下に示すように、最初に実装するupdate directを完了します.上記の動作方式では、3番の内容を以下のように表すことができます.heapify up()とheapify down()は同時にリストされますが、この2つの関数は実行されません.条件を比較するため、どちらかしか実行できません.従ってO(logn)はheap構造に修正される.
    void heap_update_direct(int i, int v)
    {
      heap[heap_index[i]].val = v;
      hepify_up(heap_index[i]);
      hepify_down(heap_index[i]);
    }

    references


    http://www.secmem.org/blog/2020/08/16/heap/
    https://blog.naver.com/sagik921123/221690373557