Title

Weak-Heap Sort

Keywords

Algorithms; data structures; E.1; F2.2; heap; priority queue

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.086013 n and the expected number is conjectured to be approximately (n-0.5)log n-0.413 n. © 1993 the BIT Foundation.

Publication Date

9-1-1993

Publication Title

BIT

Volume

33

Issue

3

Number of Pages

372-381

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/BF01990520

Socpus ID

0008799682 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0008799682

This document is currently not available here.

Share

COinS