The Violation Heap: A Relaxed Fibonacci-Like Heap

Elmasry, Amr

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

成果報告書

The Violation Heap: A Relaxed Fibonacci-Like Heap

MPS-Authors

/persons/resource/persons44380

Elmasry, Amr
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

arXiv:0812.2851.pdf
(プレプリント), 137KB

付随資料 (公開)

There is no public supplementary material available

引用

Elmasry, A. (2008). The Violation Heap: A Relaxed Fibonacci-Like Heap. Retrieved from http://arxiv.org/abs/0812.2851.

引用: https://hdl.handle.net/11858/00-001M-0000-0028-F4FF-7

要旨

We give a priority queue that achieves the same amortized bounds as Fibonacci heaps. Namely, find-min requires O(1) worst-case time, insert, meld and decrease-key require O(1) amortized time, and delete-min requires $O(\log n)$ amortized time. Our structure is simple and promises an efficient practical behavior when compared to other known Fibonacci-like heaps. The main idea behind our construction is to propagate rank updates instead of performing cascaded cuts following a decrease-key operation, allowing for a relaxed structure.