Questions tagged [priority-queues]

83 questions
50
votes
10 answers

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: remove the smallest element in the structure Common…
Alex ten Brink
  • 9,226
  • 3
  • 37
  • 63
22
votes
4 answers

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 listed for min-heap? I imagine it is possible to…
GatotPujo
  • 221
  • 1
  • 2
  • 3
19
votes
5 answers

Priority queue for partially ordered priorities with infima

I have a some objects with priority that is compound type and is only partially ordered . I need to select the objects in order of this priority (i.e. yield minimal item each time). But rather than arbitrarily completing the order, I would prefer if…
Jan Hudec
  • 658
  • 4
  • 13
16
votes
2 answers

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 number of elements in all the input lists. (Hint: Use a…
ramgorur
  • 541
  • 1
  • 5
  • 17
12
votes
1 answer

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() : returns a pointer to the element with minimum key delete-min() : removes the element with minimum key delete(node) :…
Joe
  • 4,115
  • 1
  • 22
  • 38
12
votes
2 answers

Why in a min priority queue (heap based) it is called "decrease-key" and not just "set-key"?

When you call decrease-key in a min priority queue, you are basically setting the key, you can accidentally put a higher key, right? so why isn't it called "set-key" or "update-key"? why (according to Wikipedia and other sources) a min priority…
Eran Medan
  • 431
  • 1
  • 5
  • 12
10
votes
1 answer

Would it make sense to use an array of linked lists for a Priority Queue, given a fixed number of priorities?

From what I can gather priority queues are typically implemented with heaps. If I have a small fixed number of priorities (such as 4), wouldn't a small array where each index represents the priority, and indexes into the associated linked list at…
user4779
  • 371
  • 2
  • 12
7
votes
2 answers

Lower bounds: queues that return their min elements in $O(1)$ time

First, consider this simple problem --- design a data structure of comparable elements that behaves just like a stack (in particular, push(), pop() and top() take constant time), but can also return its min value in $O(1)$ time, without removing it…
Igor Markov
  • 323
  • 2
  • 8
6
votes
1 answer

Best data structure for a queue with random reads?

Well, it's not exactly a queue if it allows for random reads. This question is about a data structure which behaves like a queue for insertions and a sorted dictionary for reads. Imagine an algorithm that maintains a list of elements so that: It…
Greg
  • 259
  • 1
  • 6
5
votes
1 answer

Heap-like data structure allowing peek at largest & smallest

For the purpose of implementing an optimization algorithm (finding the minimum of a multivariate function) I want to create a data structure that supports the following operations: load from array Peek at maximum element (but don't destroy it) Peek…
Snowbody
  • 153
  • 5
4
votes
2 answers

Devise algorithm to travel destinations in a way that you always have enough money for the next destination (getting paid at each destination as well)

This problem probably falls under some category of algorithms but I don't know which. A given restaurant has $b_1..b_n$ branches around the world. A food critic has to travel all of the branches. When the critic finishes visit to the branch $1 \le…
hitchhiker
  • 143
  • 3
4
votes
1 answer

Batch processing in increase-key function using binary heap

Is there an algorithm to perform batch processing in the increase-key operation? Let us say, a binary heap (min-heap) is used. In the normal increase-key function, if we perform increase key on one node, then we have to traverse paths from the node…
has
  • 361
  • 2
  • 5
4
votes
0 answers

Concurrent priority queue with lazy increase-key

I could use a priority queue supporting the find-and-delete-min , and lazy-increase-key operations. The last term is my "invention". It should go like this: The keys are held somewhere outside of the queue and get increased very often (more often…
maaartinus
  • 483
  • 2
  • 9
4
votes
0 answers

Does a priority queue exist with O(1) extract-min and re-insertion from removed positions?

I am envisioning a priority queue that is a bit strange. It represents wanting to do a depth-first left-to-right walk of a tree, but allowing for parallel workers where there can be time between assigning a node to a worker and getting new child…
orlp
  • 14,088
  • 1
  • 27
  • 42
4
votes
1 answer

Dijkstra without decrease key

I was reading through this paper, "Priority Queues and Dijkstra's Algorithm" by Mo Chen et al. , which suggests using Dijkstra's without edge relaxation, but to rather to just insert new nodes. Please see the pseudo code listed on the right-hand…
user3726947
  • 153
  • 1
  • 4
1
2 3 4 5 6