Brodal队列

在计算机科学中，Brodal队列是一种堆、优先队列数据结构。该数据结构有很优的最劣时间复杂度：${\displaystyle O(1)}$插入、找到最小值、合并或单点减少，${\displaystyle O\left(\mathrm {log} \left(n\right)\right)}$删除元素。这是第一种非均摊实现该复杂度的堆。其得名于发明者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).

这是一篇電腦科學小作品。您可以通过编辑或修订扩充其内容。 查 论 编