[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