Skip to content

堆 ​

cpp
__gnu_pbds::priority_queue<T, Compare = std::less<T>, 
Tag = __gnu_pbds::pairing_heap_tag, Allocator = std::allocator<char> >

__gnu_pbds::pairing_heap_tag 配对堆,在非原生元素中,该堆表现最好.

__gnu_pbds::binary_heap_tag 二叉堆,在原生元素中,该堆表现最好.

__gnu_pbds::binomial_heap_tag 二项堆(即二项队列),合并操作优于二叉堆,查询操作劣于二叉堆

__gnu_pbds::rc_binomial_heap_tag 冗余计数二项堆

__gnu_pbds::thin_heap_tag 除合并操作外与斐波那契堆一致

__gnu_pbds::Allocator 内存分配器,同上

时间复杂度对比 ​

Image