Questions tagged [priority-queues]
The priority-queues tag has no usage guidance.
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: ...
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 ...
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 ...
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() : ...
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 ...
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 ...