The priority-queues tag has no wiki summary.
1
vote
1answer
35 views
Load balancing. Why not use priority queues?
I have recently learned about various randomized algorithms for load balancing. The model is always that there are $m$ balls and $n$ bins and the balls arrive one at a time. The task is to minimize ...
2
votes
1answer
53 views
performance between the data structures
I have developed two existing data structures and I want to see their performances over a certain algorithm. In this case I use Dijkstra's algorithm with binary and Fibonacci heaps. Just to ask, if I ...
2
votes
3answers
484 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 ...
11
votes
4answers
136 views
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 ...
1
vote
2answers
70 views
Using Queues for a Stack and Stacks for a Queue
I was asked a question on how to use a pair of Queues to create a Stack and how to use a pair of Stacks to create a Queue. Any thoughts on how I would do this? Right now I don't even know where to ...
4
votes
2answers
198 views
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 ...
3
votes
1answer
136 views
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 ...
2
votes
5answers
441 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 ...
1
vote
0answers
118 views
Queue that can sort by multiple priorities?
I have a high interest in priority-queues (E.g., see my answers on: Does there exist a priority queue with $O(1)$ extracts?), and was wondering if there is a priority-queue or similar data-structure ...
1
vote
0answers
107 views
complexity of dequeueMax if implemented with unsorted vector [closed]
I am analyzing and testing a priority queue, implemented with a non-standard (non-STL in C++) vector. It is from an assignment of an online course with lots of code supplied: programming assignment 6.
...
9
votes
1answer
450 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() : ...
23
votes
9answers
2k 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: ...
