Questions tagged [priority-queues]
The priority-queues tag has no usage guidance.
80
questions
1
vote
2
answers
78
views
How can we prove that "extract almost minimum" operation in a priority queue cannot be done in o(log n)?
Suppose we want to create a priority queue with 2 operations: insert and extract almost min. Extract almost min operation selects either the first minimum or a second minimum item from the structure ...
- 31
0
votes
1
answer
40
views
Looking for name of a priority queue data structure based on bit-boundary buckets
(Note: cross-listed on stack overflow: https://stackoverflow.com/questions/73362856/looking-for-name-of-a-priority-queue-data-structure-based-on-bit-boundary-bucket)
I'm looking for the name of a data ...
- 5,722
0
votes
1
answer
51
views
Does order of elements in a set matter in Dijkstra's Algorithm?
When we use a set for doing Dijkstra's Algorithm, we use a pair of {distance,node} which we insert in a set. Most of the articles say that the first element of pair should be the distance , else we ...
0
votes
1
answer
121
views
Did I invent a new data structure?
I needed to implement a priority queue for a project I'm working on and had this idea. In a priority queue BST implementation wouldn't it be more efficient if the poll node pointed to its parent since ...
1
vote
0
answers
47
views
Priority Queues with $DecreaseKey,FindMin,Insert$ in time $O(1)$, $DeleteMin$ in $ O(\log n)$ and $IncreaseKey$ in $O(1)$, Amortized
Problem:
In this problem, we discuss Data-Structures that maintain a group of ordered elements.
We must support the operations $ DecreaseKey, FindMin, Insert $ in time $ O(1) $ and the operation $ ...
- 233
1
vote
1
answer
602
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 ...
- 111
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
3
votes
0
answers
86
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.4k
1
vote
1
answer
136
views
Indexed Priority Queue change key
So I was just studying about Indexed Priority Queues and I got confused about the increase key operation.
So basically we have the option to increase a key for an element in log n time because we can ...
2
votes
0
answers
23
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
3
votes
1
answer
186
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
2
votes
2
answers
80
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
3
votes
1
answer
63
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
2
votes
2
answers
223
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
0
votes
1
answer
153
views
Build a priority queue using dictionary
QUESTION: Can we Implementing priority queue with hash table please?
As I understand, dictionary/hash table does not have sorting mechanism inside. It adds pairs of $<key,value>$ to hash table. ...
- 459
2
votes
1
answer
163
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
1
vote
1
answer
69
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
0
votes
0
answers
21
views
How to find diffrenet ways to implement merge and delete_min operation in binomial heap?
I have searched on the internet to find different ways to learn binomial heap operations. What I have found is not quite helpful for me.For example, for delete min operation the algorithm says:
...
1
vote
2
answers
100
views
Max-Heap PriorityQueue to keep the k highest items and return them in descending order
I have created a custom implementation for PriorityQueue using max-heap and everything works fine.
But now i want to change it and keep only the k highest objects in the heap after every insertion. I ...
1
vote
1
answer
317
views
Is there an algorithm for random sampling from a priority queue with probability proportional to priority?
Suppose I want to randomly sample from a large set of items, each of which has a "score". I want my probability of sampling to be proportional to the score. One simple way to achieve this ...
- 21
0
votes
0
answers
34
views
data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure need to support the following operations
I've got this question from an exercise and i'm not sure if it is possible to do so
Think of new data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure ...
- 211
3
votes
1
answer
424
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
1
vote
1
answer
46
views
Constructing a data structure supporting prioritized key lookup
so this is more or less a shot in the dark as I am feeling stuck. Maybe some of you have an idea which helps.
Here is the problem description (pseudo formal):
I want to have a structure $T = \{ \hat{...
- 121
0
votes
0
answers
483
views
Monotone priority queues
I'm a little confused about how monotone priority queues work.
As far as I understand:
A queue is a FIFO data structure
A priority queue is a queue where the current element of highest (or lowest) ...
3
votes
2
answers
595
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 :
...
- 173
1
vote
1
answer
282
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
2
votes
1
answer
108
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/...
- 127
1
vote
0
answers
23
views
How to compute the general term formula for the number of full binary tree heaps that can be formed with distinct elements?
The number of possible heaps that are full binary trees of height $h$ and can be formed with ($n = 2^h - 1$) distinct elements can be computed by recursion:
$$ a_h = {2^h - 2 \choose 2^{h - 1} - 1} a_{...
- 145
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
3
votes
0
answers
530
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
2
votes
2
answers
297
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
3
votes
1
answer
37
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-...
- 222
0
votes
2
answers
134
views
When inserting an element in a priority queue and the heap size is already at max capacity, should you output an error OR increase the array size?
I'm currently learning about how to implement priority queues using heaps, but I've hit a wall while trying to implement the insertion operation. Assume that the size of the array storing the ...
1
vote
1
answer
110
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
0
votes
1
answer
78
views
Short Fibonacci Heap
Is it possible to create a Fibonacci Heap that has exactly 5 nodes: one root node and 4 children of that root?. If yes please explain the sequence of operations to do so. If it is not possible then ...
1
vote
1
answer
95
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
3
votes
3
answers
858
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 ...
- 374
1
vote
1
answer
79
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
515
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 ...
- 459
1
vote
1
answer
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 ...
1
vote
0
answers
85
views
How priority queue is used in Dijsktra algorithm?
I have difficulties understanding how the priority queue is used in Dijkstra algorithm. Wikipedia lists 3 operations performed on priority queue:
add_with_priority(),
extract_min(),
...
- 228
1
vote
2
answers
191
views
Sorting in a Priority Queue
Does a priority queue Queue<K,V> always sort its elements based on the value of each element or its key?
I know than the priority in the queue is based on ...
user97496
1
vote
1
answer
68
views
Complexity of closest set of points in plane problem
Given a set of points on a plane find the set of $n$ points that are closest to the origin. (Points are pairs of integers.)
Input: list of points.
Initialize a priority queue $Q$, where ...
- 111
1
vote
2
answers
158
views
Priority queue of constant size fit for extraction of K highest priority elements
In an algorithm I'm designing, I need to do this cycle on a priority queue of constant size N many times, as quickly as possible:
get $K$ highest priority elements (do on them some outside ...
- 13
2
votes
0
answers
488
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 ...
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
191
views
Leftist Tree initialization in O(n) time
In the book Handbook of Data Structures and Applications, section 5.2.5, (copy of the relevant section available here) about leftist queues, the author(s) state the following:
For the complexity ...
- 13
0
votes
0
answers
2k
views
Find K largest elements using a priority queue [duplicate]
Say we have a Priority Queue of size 1000 that is implemented using Max Heap.
Now if i want to get the top 5 elements, the most laid back method is to poll the maximum 5 times, resulting in a set of ...
- 101
0
votes
1
answer
439
views
Bucket Priority Queues with large integers for $O(1)$ insert and extract~min?
I recently got into a discussion about Priority Queues when the requirements allow for "best effort" removal (i.e. the removed key may not always be THE very highest priority, but it is relatively ...
- 101
0
votes
2
answers
92
views
Why do we need increase_key procedure in max priority queue?
Since if I want to increase the priority of a specific node, how do I find the node without linear searching it.
I need to pass the index to this function, which is in a way a bottleneck. So the ...
- 133