Weak-Heap Sort

    Authors

    R. D. Dutton

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Bit

    Keywords

    Algorithms; Data Structures; Heap; Priority Queue; Computer Science, Software Engineering; Mathematics, Applied

    Abstract

    A data structure called a weak-heap is defined by relaxing the requirements for a heap. The structure can be implemented on a 1-dimensional array with one extra bit per data item and can be initialized with n items using exactly n - 1 data element compares. Theoretical analysis and empirical results indicate that it is a competitive structure for sorting. The worst case number of data element comparisons is strictly less than (n - 1) log n + 0.086013n and the expected number is conjectured to be approximately (n - 0.5) log n - 0.413n.

    Journal Title

    Bit

    Volume

    33

    Issue/Number

    3

    Publication Date

    1-1-1993

    Document Type

    Article

    Language

    English

    First Page

    372

    Last Page

    381

    WOS Identifier

    WOS:A1993LZ68700002

    ISSN

    0006-3835

    Share

    COinS