Heaps with bits

DOI10.1016/0304-3975(95)00152-2MaRDI QIDQ671419zbMATH OpenOpenAlexFDO

Authors Svante Carlsson, Jingsen Chen, Christer Mattsson

Publication date 27 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(95)00152-2

zbMATH Keywords

parallel computationcomplexity heap operations heapsortfine-heappriority queue operations

Mathematics Subject Classification ID

Searching and sorting (68P10) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 1555945
• Parallel heap operations on an EREW PRAM
• Heaps on Heaps
• Parallel heap: an optimal parallel priority queue

Cites work

• scientific article; zbMATH DE number 4155887 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• A variant of heapsort with almost optimal number of comparisons
• Average-case results on heapsort
• BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
• Building heaps fast
• Building heaps in parallel
• Deleting the root of a heap
• Finding the median
• Heaps on Heaps
• Inserting a new element into a heap
• On Parallel Searching
• Parallel algorithms for priority queue operations
• Parallel heap operations on an EREW PRAM
• Searching, Merging, and Sorting in Parallel Computation
• The Analysis of Heapsort
• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• Weak-heap sort

Cited in

(12)

• An efficient data structure for branch-and-bound algorithm
• Building heaps in parallel
• A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort
• An in-place priority queue with \(O(1)\) time for push and \(\lg n + O(1)\) comparisons for pop
• scientific article; zbMATH DE number 4014031 (Why is no real title available?)
• Optimal parallel construction of heaps
• scientific article; zbMATH DE number 1555945 (Why is no real title available?)
• Thin heaps, thick heaps
• Sorting using heap structure
• The heap-mergesort
• Optimizing binary heaps
• Building heaps fast

Describes a project that uses

Uses Software

• heapsort

This page was built for publication: Heaps with bits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q671419)