User:EtaoinWu/Brodal队列

维基百科,自由的百科全书
跳到导航 跳到搜索

计算机科学中,Brodal队列是一种优先队列数据结构。该数据结构有很优的最劣时间复杂度插入、找到最小值、合并或单点减少,删除元素。这是第一种非均摊实现该复杂度的堆。其得名于发明者Gerth Stølting Brodal[1]

虽然该结构具有优越的渐进复杂度,Brodal本人表示它“很复杂”,“不适合实践”。Brodal和Okasaki也发明过一个可持久化的Brodal队列变种。[2]

参考文献[编辑]

  1. ^ Gerth Stølting Brodal (1996).
  2. ^ Gerth Stølting Brodal and Chris Okasaki (1996).