Radix Heap
(data-structure/radix-heap.hpp)
Radix Heap
概要
Radix Heap(基数ヒープ)とは、単調順位ヒープ(追加した値が最後に取り出した値より大きい必要があるヒープ)の一種である。std::priority_queue
と比べて定数倍が軽いことからDijkstra法に用いて定数倍高速化に使用される。
使い方
-
RadixHeap<Key, Val>()
: コンストラクタ。Key
は整数型のみを取る。
-
push(Key, Val)
: ヒープにpushする。
-
pop()
: ヒープの要素のうち最小のものをpopして返す。
-
size()
: ヒープ内の要素数を返す。
-
empty()
: ヒープが空かどうかを返す。
Required by
Verified with
Code
Back to top page