はじめに

ダイクストラ法などを実装したいときには、

myenigma.hatenablog.com

Openセットの中で毎回コストが最小のノードを選択する必要がありますが、

毎回ノードの最小値を検索しても良いですが、

より効率的に最小のノードを選択する方法として、

優先度付きキューを使う方法があります。

ufcpp.net

今回の記事では、この優先度付きキューの概要と

サンプル実装について紹介したいと思います。

優先度付きキュー(ヒープ)の概要

優先度付きキュー(Priority queue)は、

二分ヒープとも呼ばれるデータ構造の一種で、

データを追加した時に、

O(logN)で自動的にソートする事ができるキューです。

少しずつキューにデータを入れて、

その都度、最もコストが大きい(小さい)データを

利用したいときに効率的に処理できます。

(末尾のベンチマークの結果をご確認ください)

この優先度付きキューは二分木の形で表現され、

子の２つの値は、親の値よりも小さくなるように格納することにより、

効率的にソートされるようにできます。

ja.wikipedia.org

medium.com

例えば、ある値を追加するときは、

二分木の一番右下に追加し、

親の値と比較して、大きかったら、

親と値を交換することを繰り返しながら、

ソートされた状態をキープします。

詳細は上記のリンクの記事を参照ください。

優先度付きキューの各処理の計算量

処理	平均計算量	最悪計算量
値xを挿入する(自動的にソートされる)	O(1)	O(logN)
最大値を取得する	O(1)	O(1)
最小値を取得する	O(1)	O(1)
最大値を削除する	O(logN)	O(logN)
最小値を削除する	O(1)	O(1)

Juliaによる実装

下記は優先度付きキューをJuliaで実装してみた例です。

struct PriorityQueue{K, V}
    values::Array{Pair{K,V}}
    PriorityQueue{K,V}() where {K,V} = new(Array{Pair{K,V}}(undef, 0))
end

function push!(pq::PriorityQueue{K,V}, pair::Pair{K,V}) where {K,V}
    Base.push!(pq.values, pair)
    index = length(pq.values)
    while index > 1
        parent_index = div(index - 1, 2) + 1
        (pq.values[parent_index].first >= pair.first) && break
        pq.values[index] = pq.values[parent_index]
        index = parent_index
    end
    pq.values[index] = pair
    return nothing
end

function pop_highest!(pq::PriorityQueue)
    isempty(pq.values) && return nothing
    max_value = highest(pq) 
    value = pop!(pq.values)
    index = 1
    while (index * 2) <= length(pq.values)
        cind1, cind2 = index * 2, index * 2 + 1
        flag = (cind2 >= length(pq.values) || pq.values[cind1] > pq.values[cind2]) 
        bigger_index = flag ? cind1 : cind2
        pq.values[bigger_index] <= value && break
        pq.values[index] = pq.values[bigger_index]
        index = bigger_index
    end
    pq.values[index] = value
    return max_value
end

pop_lowest!(pq::PriorityQueue) = !isempty(pq.values) ? pop!(pq.values) : nothing
highest(pq::PriorityQueue) = !isempty(pq.values) ? pq.values[1] : nothing
lowest(pq::PriorityQueue) = !isempty(pq.values) ? pq.values[end] : nothing