Heaps with bits

DOI10.1016/0304-3975(95)00152-2zbMath0874.68084OpenAlexW1991074482MaRDI QIDQ671419

Christer Mattsson, Svante Carlsson, Jingsen Chen

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)

Related Items (6)

An In-Place Priority Queue with O(1) Time for Push and $$\lg n + O(1)$$ lg n + O ( 1 ) Comparisons for Pop ⋮ Optimizing binary heaps ⋮ Sorting using heap structure ⋮ An efficient data structure for branch-and-bound algorithm ⋮ A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort ⋮ The heap-mergesort

Uses Software

• heapsort

Cites Work

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

This page was built for publication: Heaps with bits