Questions tagged [priority-queues]
The priority-queues tag has no usage guidance.
18
questions with no upvoted or accepted answers
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
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
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
0
answers
62
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
361
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 ...
1
vote
0
answers
24
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
1
vote
0
answers
96
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
0
votes
0
answers
14
views
M/G/1 (?) with server vacations
I'm asking your help to solve this:
Consider a time-division multiplexor that multiplexes $30$ input packet streams onto a outgoing link with a slot time of $4 \mu s$. Assume that the packet arrival ...
- 101
0
votes
0
answers
26
views
M/M/1 priority queueing system (?), an exercise
can someone help me please solving this?
Consider a switch with two input links and one outgoing transmission link. Data packets arrive at the first input link according to a Poisson process with mean ...
- 101
0
votes
0
answers
24
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:
...
0
votes
0
answers
36
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
0
votes
0
answers
560
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) ...
0
votes
0
answers
3k
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 ...
- 109
0
votes
0
answers
1k
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 ...
- 968