EurekaMoments

This is my studying logs about Autonomous driving, Machine learning technologies and etc.

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

目次

目的

  • データ構造の一種である優先度つき待ち行列(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つとなる。
  • 大小比較の結果、子ノードより大きかった場合は両者の順番を入れ替える。
  • 子ノード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

サンプル実行結果

  • まずはランダムに10個の整数を生成し、アップヒープでソートしながらキューに溜めていく。
  • 一つ整数が追加されるたびにソートが実行され、先頭の最小値が更新されている事が分かる。
    f:id:sy4310:20201031202201p:plain
  • そして最後にダウンソートしながら先頭の整数を順次取り出していった結果がこちら。
    f:id:sy4310:20201031203527p:plain
  • これをツリー構造で表現し直すとこちらのようになる。
  • このことから、優先度つき待ち行列を利用することで、各ノードの優先度に基づいた幅優先探索ができるようになることが分かる。 f:id:sy4310:20201031205010p:plain

GitHub

  • 記載したサンプルコードはこちらのGitHubリポジトリで公開中。

github.com