The relaxed min-max heap: A mergeable double-ended priority queue (Q1323336): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
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
    0 references
    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

    Identifiers