Heaps with bits

DOI10.1016/0304-3975(95)00152-2zbMath0874.68084MaRDI 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 computation; complexity heap operations heapsort; fine-heap; priority queue operations

Mathematics Subject Classification ID

68P10: Searching and sorting

68W15: Distributed algorithms

Related Items

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

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