Questions tagged [priority-queues]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
50 votes
9 answers
16k 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: ...
Alex ten Brink's user avatar
22 votes
4 answers
52k 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 ...
GatotPujo's user avatar
  • 221
16 votes
2 answers
41k 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 ...
ramgorur's user avatar
  • 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() : ...
Joe's user avatar
  • 4,107
3 votes
5 answers
10k 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 ...
A T's user avatar
  • 968
2 votes
0 answers
534 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 ...
Claudia's user avatar
  • 121