{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T06:38:58Z","timestamp":1784011138473,"version":"3.55.0"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1142\/s1793830910000838","type":"journal-article","created":{"date-parts":[[2011,1,17]],"date-time":"2011-01-17T03:21:26Z","timestamp":1295234486000},"page":"493-503","source":"Crossref","is-referenced-by-count":4,"title":["THE VIOLATION HEAP: A RELAXED FIBONACCI-LIKE HEAP"],"prefix":"10.1142","volume":"02","author":[{"given":"AMR","family":"ELMASRY","sequence":"first","affiliation":[{"name":"Max-Planck Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","first-page":"263","volume":"146","author":"Adelson G.","journal-title":"Doklady Akademia Nauk SSSR"},{"key":"rf3","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"2001"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/50087.50096"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-008-0070-7"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320214"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840439"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"rf15","volume":"4","author":"Kaplan H.","journal-title":"ACM Trans. Algorithms"},{"key":"rf17","first-page":"99","volume":"15","author":"Moret B.","journal-title":"Disc. Math. Theor. Comp. Sci."},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1145\/214748.214759"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00219-6"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1145\/359460.359478"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830910000838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T13:15:54Z","timestamp":1565097354000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830910000838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":13,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1142\/S1793830910000838"],"URL":"https:\/\/doi.org\/10.1142\/s1793830910000838","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}