The relaxed min-max heap: A mergeable double-ended priority queue (Q1323336): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Min-max heaps and generalized priority queues / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Implementation and Analysis of Binomial Queue Algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The pairing heap: A new form of self-adjusting heap / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A pointer-free data structure for merging heaps and min-max heaps / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bounds for min-max heaps / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Self-Adjusting Heaps / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A data structure for manipulating priority queues / rank | |||
Normal rank |
Revision as of 14:46, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The relaxed min-max heap: A mergeable double-ended priority queue |
scientific article |
Statements
The relaxed min-max heap: A mergeable double-ended priority queue (English)
0 references
10 May 1994
0 references
A data structure that implements a mergeable double-ended priority queue, namely the relaxed min-max heap, is presented. A relaxed min-max heap of \(n\) items can be constructed in \(O(n)\) time. In the worst case, operations \textit{find-min}( ) and \textit{find-max}( ) can be performed in constant time, while each of the operations \textit{merge}( ), \textit{insert}( ), \textit{delete-min}( ), \textit{decrease-key}( ), and \textit{delete-key}( ) can be performed in \(O(\log n)\) time. Moreover, \textit{insert}( ) has \(O(1)\) amortized running time. If lazy merging is used, \textit{merge}( ) will also have \(O(1)\) worst-case and amortized time. The relaxed min-max heap is the first data structure which achieves these bounds using only two pointers per item.
0 references
data structure
0 references
priority queue
0 references
relaxed min-max heap
0 references