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

From MaRDI portal
Revision as of 10:17, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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