跳至內容

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).