跳转到内容

Brodal队列

维基百科,自由的百科全书

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

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

参考文献

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