Questions tagged [priority-queues]
The priority-queues tag has no usage guidance.
1
vote
1answer
25 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 ...
0
votes
1answer
47 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
1answer
43 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 ...
1
vote
1answer
40 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).
...
2
votes
2answers
304 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 ...
0
votes
1answer
101 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
0answers
29 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(),
...
1
vote
2answers
50 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 ...
1
vote
1answer
40 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 ...
1
vote
2answers
45 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 ...
2
votes
0answers
292 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
2answers
132 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 ...
1
vote
1answer
110 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 ...
0
votes
1answer
273 views
How to read off the set represented by a van-Emde-Boas tree?
I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...
0
votes
0answers
793 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 ...
0
votes
1answer
199 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 ...
0
votes
2answers
64 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 ...
4
votes
2answers
177 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.
...
0
votes
0answers
1k views
Bubble down implementation for min-heap
While going through bubble_down implementation for min-heap in The Algorithm Design Manual By Steven Skiena, since routine ...
1
vote
2answers
503 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 ...
3
votes
0answers
305 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 ...
6
votes
1answer
306 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 ...
2
votes
1answer
54 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 ...
2
votes
2answers
5k 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?
7
votes
1answer
5k 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 ...
4
votes
1answer
605 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
...
0
votes
2answers
6k views
How to calculate probability of packet loss and drop rate?
In a queuing system (M/M/1) with a finite packet capacity $z$, how do you determine the probability of packet loss if we assume that packets are dropped when the system is full? Packets arrive with a ...
2
votes
0answers
3k 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?...
0
votes
1answer
87 views
What will trigger a worst time search for a binary heap and what is the run time? [closed]
I thought if the values in a max or min heap is monotonically increasing or decreasing, then this will trigger a worst case run time of $\mathcal{O}(n)$ because you will have to go through each and ...
0
votes
0answers
624 views
Dynamically weighted priority queue?
Elements are stored in a single dynamic data-structure $D$
Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$
The function $f$ is weighting based on the value of ...
4
votes
0answers
248 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 "...
3
votes
1answer
544 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\...
1
vote
2answers
107 views
“Minimum Stack”
I am now preparing for a test in my algorithms course and I have stumbled upon a question about a data structure which seems too trivial for me, but is probably not trivial at all.
The question is:
...
3
votes
2answers
2k 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|...
1
vote
1answer
858 views
Which priority queue implementations are stable?
I can't answer this question. It seems simple but I really don't know how to approach it.
Here it is:
A priority queue is said to be stable if deletions of items with equal priority value occur in ...
14
votes
2answers
28k 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 ...
1
vote
3answers
618 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 ...
2
votes
1answer
1k 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
86 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 ...
16
votes
3answers
34k 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 ...
16
votes
6answers
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 ...
5
votes
2answers
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 ...
4
votes
1answer
407 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
6k 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 ...
3
votes
1answer
2k 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 ...
11
votes
1answer
3k 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() : ...
45
votes
9answers
10k 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: ...
