Questions tagged [priority-queues]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
2answers
60 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 ...
1
vote
1answer
36 views

What is the anayslsis that a heap's optimal branching factor is 2 <= factor <=5?

I'm reading the book Advanced Algorithms and Data Structures and it makes the claim that the optimal branching factor for a heap is 2 <= D <= 5 and that it is ...
2
votes
2answers
56 views

Given n positive integers, pick two elements and subtract each by one with one operation. Find max 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 ...
0
votes
1answer
30 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. ...
0
votes
0answers
21 views

Accessing Array-based vs LinkedList PriorityQueue

Question 1: Suppose we have the two priority queues, or we have two implementations available. One implementation uses an array to maintain the entries in the priority queue, while the other uses a ...
2
votes
1answer
37 views

Dijkstra's Algorithm Same Node Added Multiple Times to Priority Queue

In the this discussion of Dijkstra's Algorithm appear the following comments: ...
1
vote
1answer
58 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 ...
0
votes
0answers
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
2answers
75 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
1answer
116 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 ...
0
votes
0answers
30 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 ...
3
votes
1answer
267 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 ...
1
vote
1answer
35 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{...
0
votes
0answers
368 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
2answers
446 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 : ...
1
vote
1answer
236 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? ...
2
votes
1answer
83 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/...
1
vote
0answers
22 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_{...
4
votes
1answer
948 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 ...
3
votes
0answers
485 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, ...
2
votes
2answers
151 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 ...
3
votes
1answer
33 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-...
0
votes
2answers
87 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
1answer
99 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
75 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
82 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 ...
3
votes
3answers
727 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 ...
1
vote
1answer
67 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). ...
1
vote
2answers
489 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 ...
1
vote
1answer
1k 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
75 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
163 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
54 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
142 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
464 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
812 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
175 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
0answers
1k 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
396 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
78 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
185 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
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 ...
1
vote
2answers
806 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 ...
2
votes
0answers
403 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
562 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
57 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 ...
1
vote
2answers
9k 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?
10
votes
2answers
8k 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 ...
5
votes
1answer
869 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
8k 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 ...