priority_queue

priority_queue とは priority_queueとは優先度つき待ち行列と呼ばれるもので、 挿入された順序どおりに要素の取り出しを行うのではなく、 優先度の高い要素から先に取り出す待ち行列。 例えば、int型を格納するpriority_queueで、整数の値をそのまま優先度として用いると、値の大きな整数から順に取り出される待ち行列になります。 priority_queueはヒープと呼ばれるデータ構造が使われます。 このヒープは、完全な2分木の形をしていて、 木の各ノードは自身より下にの要素よりも大きな値を持ちます。 そのため、最大の値を持つ要素は常に木の根に含まれていることになります。 この木の根にある要素を取り出すことで常に最大の値を持つ要素を取り出します。 ヒープの実装は、ランダムアクセス([]を使った添字によるアクセス)のできるデータ構造を使って行えます。 STL にお