優先度つき待ち行列(Priority Queue)の概要とJuliaサンプルコード

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者:渡部有隆
発売日: 2015/01/30
メディア: Kindle版

目的

データ構造の一種である優先度つき待ち行列(Priority Queue)の特徴について理解する。
優先度つきキューを利用したソートを行うサンプルコードを実装して動作を確認する。

前提知識

待ち行列(キュー)

www.cc.kyoto-su.ac.jp

レジなどで順番待ちをする人の列のような形でデータを蓄えておくためのデータ構造。
新たにデータが追加された際は、待ち行列の最後尾に加わる。
待ち行列の先頭からデータ(最初に追加されたもの)を取り出す。
先入れ先出し法(First In First Out)と呼ばれる。

ヒープ

www.codereading.com

親ノードが子ノードよりも小さい(あるいは大きい)か等しいという関係を満たすツリーで表現したデータ構造。
ヒープは配列を使って表現され、これを用いて要素を整列するアルゴリズムをヒープソートという。
あるノードが追加された際、それの親ノードと比較しながら上流に向かってソートしていくことをアップヒープという。
それに対して、その子ノードと比較しながら下流に向かってソートしていくことをダウンヒープという。

優先度つき待ち行列

www.nct9.ne.jp

概要

各ノードが持つデータに優先度をつけ、それを基準にヒープを構築する。
優先度が高いものほどキューの先頭側にいくようにソートすることで、First In First Outで優先度が高いものから取り出されるようになる。

Juliaサンプルコード

全体

module PQ
    using StatsBase

    buffer = []

    # move added node to root
    function upheap(buffer, n)
        while true
            p = Int(trunc((n - 1)/2))
            if (p < -1) || (buffer[p+1] <= buffer[n+1])
                break
            end
            tmp = buffer[n+1]
            buffer[n+1] = buffer[p+1]
            buffer[p+1] = tmp
            n = p
        end
    end

    # move root node to leaf
    function downheap(buffer, n)
        len = length(buffer)
        while true
            c = 2 * n + 1
            if c >= len
                break
            end
            # exchange parent and smaller child
            if (c + 1) < len
                if buffer[c+1] > buffer[c+2]
                    c += 1
                end
            end
            if buffer[n+1] <= buffer[c+1]
                break
            end
            tmp = buffer[n+1]
            buffer[n+1] = buffer[c+1]
            buffer[c+1] = tmp
            n = c
        end
    end

    # add data to tail of buffer
    # after adding, sort as upheap
    function push(buffer, data)
        push!(buffer, data)
        upheap(buffer, length(buffer)-1)
    end

    # get minimum data
    function peek(buffer)
        return buffer[1]
    end
    
    # get and remove minimum data
    function pop(buffer)
        min_val = buffer[1]
        last_val = buffer[end]
        deleteat!(buffer, length(buffer))
        if length(buffer) > 0
            # create heap again
            buffer[1] = last_val
            downheap(buffer, 0)
        end
        return min_val
    end

    function main()
        input = sample(1:100, 10, replace=false)
        # create by upheap
        for n in input
            push(buffer, n)
            println("Add $(n), Min data = $(peek(buffer))")
        end
        # remove minimum data and create by downheap
        while length(buffer) > 0
            print("$(pop(buffer)) ")
        end
    end
end

if abspath(PROGRAM_FILE) == @__FILE__
    using .PQ
    PQ.main()
end

メイン処理

最初にランダムに10個の整数配列を生成する。
各整数を順番にキューに入れていき、その度にアップヒープでソートする。(push関数)
その後、キューの先頭から順番に取り出していき、その度にダウンヒープでソートする。(pop関数)

function main()
    input = sample(1:100, 10, replace=false)
    # create by upheap
    for n in input
        push(buffer, n)
        println("Add $(n), Min data = $(peek(buffer))")
    end
    # remove minimum data and create by downheap
    while length(buffer) > 0
        print("$(pop(buffer)) ")
    end
end

アップヒープによるソート

push関数でキューの最後尾に追加された整数を、その親ノードに位置する整数と比較する。
こういった構造を配列で表現する場合、インデックスnにあるノードから見た親ノードは(n-1)/2に位置するようになる。
(n-1)/2は小数点以下を切り捨てる。
追加したノードと親ノードを比較し、親ノードより小さい場合は入れ替えていく事でソートする。

# move added node to root
function upheap(buffer, n)
    while true
        p = Int(trunc((n - 1)/2))
        if (p < -1) || (buffer[p+1] <= buffer[n+1])
            break
        end
        tmp = buffer[n+1]
        buffer[n+1] = buffer[p+1]
        buffer[p+1] = tmp
        n = p
    end
end

push関数

キューの最後尾に要素を追加する。
追加したところで上記のアップヒープ関数を呼び出し配列全体をソートする。

# add data to tail of buffer
# after adding, sort as upheap
function push(buffer, data)
    push!(buffer, data)
    upheap(buffer, length(buffer)-1)
end

pop関数

アップヒープのソートにより、一番小さい整数がキューの先頭にある。
キューの先頭にある整数を取り出し後、残りの整数をダウンヒープでソートし直すことで、常に一番小さい整数から取り出せるようにする。

# get and remove minimum data
function pop(buffer)
    min_val = buffer[1]
    last_val = buffer[end]
    deleteat!(buffer, length(buffer))
    if length(buffer) > 0
        # create heap again
        buffer[1] = last_val
        downheap(buffer, 0)
    end
    return min_val
end

ダウンヒープによるソート

キューの先頭にある整数の子ノードにあたる整数を参照し、大小を比較する。
インデックスnにあるノードに対する子ノードのインデックスは2n+1と2n+2の２つとなる。
大小比較の結果、子ノードより大きかった場合は両者の順番を入れ替える。
子ノード2つの内、より小さい方のノードが親との入れ替え対象になる。
親ノードより子ノードの方が大きいという関係が成立するようになるまでソートを繰り返す。

# move root node to leaf
function downheap(buffer, n)
    len = length(buffer)
    while true
        c = 2 * n + 1
        if c >= len
            break
        end
        # exchange parent and smaller child
        if (c + 1) < len
            if buffer[c+1] > buffer[c+2]
                c += 1
            end
        end
        if buffer[n+1] <= buffer[c+1]
            break
        end
        tmp = buffer[n+1]
        buffer[n+1] = buffer[c+1]
        buffer[c+1] = tmp
        n = c
    end
end