Questions tagged [priority-queues]
The priority-queues tag has no usage guidance.
6
questions
50
votes
9
answers
15k
views
Does there exist a priority queue with $O(1)$ extracts?
There are a great many data structures that implement the priority-queue interface:
Insert: insert an element into the structure
Get-Min: return the smallest element in the structure
Extract-Min: ...
- 9,006
22
votes
3
answers
50k
views
Increase-key and decrease-key in a binary min-heap
In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally ...
- 221
16
votes
2
answers
39k
views
Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list
Most probably, this question is asked before. It's from CLRS (2nd Ed) problem 6.5-8 --
Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total ...
- 541
12
votes
1
answer
5k
views
Priority queue with both decrease-key and increase-key operations
A Fibonnaci Heap supports the following operations:
insert(key, data) : adds a new element to the data structure
find-min() : ...
- 4,037
3
votes
5
answers
9k
views
Most efficient known priority queue for inserts
In terms of asymptotic space and time complexity, what is the most efficient priority-queue?
Specifically I am looking for priority queues which minimize the complexity of inserts, it's ok if deletes ...
- 968
2
votes
0
answers
498
views
Unique integer priority queue with both $O(1)$ insert and extract-min?
I'm aware of the two questions prioritizing inserts and extracts individually, each in $O(1)$ time, but does there exist a unique integer priority queue algorithm for the range $[0, n)$ that can do ...
- 121