Questions tagged [priority-queues]
The priority-queues tag has no usage guidance.
83
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
19
votes
5
answers
1k
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 ...
- 658
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
11
votes
2
answers
10k
views
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 ...
- 421
10
votes
1
answer
2k
views
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, ...
- 381
6
votes
2
answers
2k
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 ...
- 313
6
votes
1
answer
691
views
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 ...
- 239
5
votes
1
answer
999
views
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
...
- 153
4
votes
1
answer
492
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 ...
- 361
4
votes
1
answer
2k
views
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 ...
- 153
4
votes
2
answers
190
views
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.
...
- 143
4
votes
0
answers
133
views
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 ...
- 12.5k
4
votes
0
answers
289
views
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 "...
- 473
3
votes
2
answers
669
views
What are the disadvantages of Fibonacci Heaps?
A Fibonacci heap is a data structure for priority queue / heap operations. It seems to have the best complexity for all operations:
Since it has the best performance, why not use it everywhere?
What ...
- 143
3
votes
3
answers
910
views
Merging balls interview problem
Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks.
You are given $n$ balls on the table and all the balls are rolling towards the ...
- 394
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
3
votes
2
answers
2k
views
Why is a heap better than a linked list for implementation of a priority queue?
Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal.
Why is it better to have log-n for both than n for one and constant ...
3
votes
1
answer
628
views
Can we create binomial heaps in linear time?
I'm studying binomial heaps in anticipation for my finals and the CLRS book tells me that insertion in a binomial heap takes $\Theta(\log n)$ time. So given an array of numbers it would take $\Theta(n\...
- 339
3
votes
2
answers
3k
views
Priority queue with unique elements and sublinear time merge?
Some priority queues, like the height-based leftist tree (or here) support merging in $\mathcal O\left(\log n\right)$ time.
I am looking for a priority queue that merges in (expected|average|...
- 6,171
3
votes
1
answer
195
views
Designing a Queue that efficiently tracks position
Suppose we want to construct a queue with the following properties:
The priority of each member of the queue must be known. For example, for the head node, their priority is 1, for the next node, ...
- 314
3
votes
1
answer
40
views
Parallelization of priority queue-based algorithms
There's a number of algorithms that operate by maintaining and consuming a priority queue of "events". I'm thinking primarily of geometric algorithms, particularly sweep-line algorithms like Bentley-...
- 221
3
votes
1
answer
3k
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 ...
- 968
3
votes
2
answers
812
views
Implementing an efficent priority queue using only stacks
Is it possible to implement an efficient priority queue (as efficient as a heap) only using the stack data structure?
The usual efficiency for a priority queue which is implemented using a heap is :
...
- 370
3
votes
1
answer
66
views
What is the analysis that a heap's optimal branching factor is between 2 and 5?
I'm reading the book Advanced Algorithms and Data Structures. It makes the claim that the optimal branching factor $D$ for a heap satisfies $2 \le D \le 5$, and that it is most likely $3$ or $4$ ...
- 131
3
votes
0
answers
550
views
Making an array increasing by modifying elements
I am trying to solve a problem on codeforces. Given an integer array $a_1,\ldots,a_n$, our goal is to find the minimal number of instructions, each of which increments or decrements a single entry, ...
- 41
3
votes
0
answers
6k
views
Where To Put Duplicates in Max Heap?
Question:
Suppose you have a list of integers and it might contain duplicates. Build a Max Heap using this list. Where would the duplicates of the max integer reside in this Max Heap data structure?...
- 131
2
votes
2
answers
176
views
If both could be implemented with the other, what are the differences between priority queues and binary heaps?
I've red that a binary heap can be implemented using a priority queue. I've also red the opposite, that a priority queue can be implemented using a binary heap.
This seems strange to me as ...
- 153
2
votes
1
answer
771
views
What is the amortized cost of pulling top K elements from a priority queue?
To pop an element off of a priority queue, the worst-case complexity is:
O(logN) where N is the number of elements.
Now if you do K pop operations on the priority ...
- 115
2
votes
2
answers
512
views
Given n positive integers, pick two elements and subtract each by one with one operation. Find maximum number of operations
Problem Description: We have an array of $n$ positive integers and in one operation we have to choose two elements in the array and decrease them by $1$. (Elements on which we are performing this ...
- 21
2
votes
1
answer
58
views
Efficient haircuts
I have a real vector $v$. From this vector, I want to extract a sequence of integers, $ix$. The first integer is found by, $ix_0=argmax(v)$. 1 is then subtracted from $v_{ix_0}$, and the process is ...
- 151
2
votes
1
answer
390
views
Dijkstra's Algorithm Same Node Added Multiple Times to Priority Queue
In the this discussion of Dijkstra's Algorithm appear the following comments:
...
- 255
2
votes
1
answer
2k
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 ...
- 23
2
votes
2
answers
475
views
Why can't we replace Dijkstra's priority queue with a regular queue?
I am confused why we can't simply use a normal queue instead of a priority queue for Dijkstra's. I agree that you can find the shortest path in fewer iterations of the while loop using a priority ...
- 21
2
votes
1
answer
95
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
0
answers
29
views
Is there a review of lock free priority queues for single consumer multiple producer?
Background
The task I have at hand is to write an event scheduler. From what I understood, it is basically a priority queue which needs to support concurrent insertions and single threaded delete ...
- 121
2
votes
0
answers
521
views
How would a priority queue be implemented in a functional programming language?
How would a priority queue be coded efficiently in a functional programming language? I'm new to functional programming, but I'm having difficulty understanding how a data structure that seems to ...
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
1
vote
2
answers
10k
views
Finding the median in a heap
Given a binary heap $H$, indexed in $[1..n]$, whose elements are integers, is there a way to quickly find its median in $O(\log n)$-time?
- 129
1
vote
2
answers
536
views
Is there a name for this priority queue data structure?
While watching a sports tournament, I noticed that the tournament tree looks a lot like a heap. I came up with the following data structure: A complete binary tree where the leaves are elements of ...
- 479
1
vote
3
answers
815
views
Priority queue with ubounded number of elements (i.e., with dynamic storage)
I'm looking for a data structure that can work as a priority queue with reasonable maintenance complexities (like $O(\log n)$ for insertion and deletion) and that has a theoretical unbounded limit for ...
- 141
1
vote
2
answers
871
views
How to classify simple priority queue algorithm
I have a simple priority queue algorithm that I implemented, and I doubt it's new
but I haven't been able to classify it. Wondering if I could get some help with classifying it! Once I classify it I ...
1
vote
1
answer
90
views
Minimum time to finish all meetings
what algorithm would you use to solve this problem which I recently faced in an interview?
There's a council where people go to have meetings. A person comes at time x and needs to be in a meeting for ...
- 111
1
vote
1
answer
88
views
Heap operating in time $\Gamma^{-1}(n)^2$
I have a priority queue implementation which I claim has the following worst case asymptotic run-times for the given operations:
PEEK_MIN …………………………… O(1)
POP_MIN…………………………… O( (INVERSE_Γ(n)) ^2).
...
- 621
1
vote
2
answers
1k
views
Correct term for a priority queue with unique elements
Is there a standard term for a priority queue which can only hold a single occurrence of any element? This would be a priority queue for which operations such as "raise the priority of element ...
- 251
1
vote
1
answer
317
views
Priority Queue Using Stack
Can one build a priority queue using stacks, such that the priority queue has the same complexity for each operation.
Could it be done? If so how? If not what is the best solution that can be done?
...
- 101
1
vote
1
answer
119
views
Numerical Accuracy & Sorting Algorithms?
Sedgewick and Wayne talk about how sorting algorithms and, specifically, priority queues are used in devising ways to improve accuracy in floating-point calculations: https://algs4.cs.princeton.edu/...
- 117
1
vote
1
answer
118
views
Priority queue with a buffer for delayed insertion and other tweaks
I was thinking of ways to optimise a (heap-based) priority queue in certain scenarios, like in best-first path search algorithms (Dijkstra, A*, etc.).
One possible optimisation is to delay insertions ...
- 251
1
vote
1
answer
102
views
An algorithm to drop low-priority items from a heap-based priority queue
I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value. (Or, equivalently, to drop from a priority queue realised by such a heap ...
- 251