# Questions tagged [priority-queues]

The tag has no usage guidance.

82 questions
Filter by
Sorted by
Tagged with
1 vote
43 views

### Algorithm to sort array into K increasing subsets?

Let's say we got an array of size n with real numbers, and a natural number k. n must be multiple of k. We want to sort the array in a way that, when we divide this array into k subsets of equal size, ...
1 vote
810 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
2k 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 ...
52k 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 ...
872 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 ...
97 views

### Can you simulate the following process in $O(N.log N)$

Given an array $A[]$ of N integers. pseudocode: Traverse from left to right of this array. Let's say you are standing at index $j$. For each index i=1 to i=j-1, increment all $A[i]$ by $1$ if and ...
167 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 ...
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
163 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 ...
90 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 ...
498 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 ...
138 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
84 views

28 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: ...
763 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 ...
1 vote
308 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 ...
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 ...
39 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 ...
280 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 ...
11k 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 ...
676 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) ...
1k 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
359 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? ...
1 vote
151 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
27 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_{...
611 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, ...
794 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 ...
1 vote
555 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 ...
57 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-...
1 vote
135 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 ...
92 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
116 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
97 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
134 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
396 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
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 ...
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 ...