Skip to main content
16 votes
Accepted

Would it make sense to use an array of linked lists for a Priority Queue, given a fixed number of priorities?

Not only does it make sense, it's a common data structure in operating systems to implement the ready queue for tasks. Operating systems typically have a fixed number of priority levels, so it makes ...
Pseudonym's user avatar
  • 22.2k
8 votes
Accepted

Best data structure for a queue with random reads?

Take any dictionary data structure and link its entries in whichever order suits you. In essence, you retain the $\Theta$-costs from the basic structure. In search trees, this is called threading. It ...
Raphael's user avatar
  • 72.6k
6 votes

Is there a name for this priority queue data structure?

This is essentially a Segment tree which is a data structure that augments an array with a binary tree as you describe such that: You have fast set and get at any index You have fast "aggregate" ...
Curtis F's user avatar
  • 1,043
6 votes
Accepted

What are the disadvantages of Fibonacci Heaps?

$O(1)$ merely means that no matter how large your heap grows, the operation will always take roughly the same time to execute. It doesn't mean "the fastest". Wikipedia article you linked has ...
Dmitri Urbanowicz's user avatar
6 votes

If both could be implemented with the other, what are the differences between priority queues and binary heaps?

Based on standard usage of the terms, a heap is a specific data structure, with a specific representation in memory. A priority queue is an abstract data type: it identifies some operations that must ...
D.W.'s user avatar
  • 161k
5 votes

What is the amortized cost of pulling top K elements from a priority queue?

Big-O doesn't care about a factor 0.5, for example. Now log sqrt(N) = 1/2 log N. So if you take away enough elements to change the size of the queue from N to sqrt(N), you have multiplied the time by ...
gnasher729's user avatar
  • 30.5k
4 votes
Accepted

Merging balls interview problem

Keep all the values $\frac{D_i - D_{i+1}}{V_i - V_{i+1}}$ in a min-heap. At each step, remove the minimum value, say $T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$. We would first like to update all ...
Yuval Filmus's user avatar
3 votes

Dijkstra without decrease key

You are right. Checking k < d[u] is not sufficient and updating d[u] on the next line is not necessary. The check prevents ...
Ryoji's user avatar
  • 419
3 votes
Accepted

Parallelization of priority queue-based algorithms

Two old, but, I think, still very useful resources: M.T.Goodrich, M.R.Ghouse, and J.Bright. Sweep Methods for Parallel Computational Geometry. Algorithmica (1996), 15:126-153. - closely related to ...
HEKTO's user avatar
  • 3,098
3 votes

Heap operating in time $\Gamma^{-1}(n)^2$

Stirling's formula states that $\Gamma(m) = \exp \Theta(m\log m)$. Suppose that $m = \Gamma^{-1}(n)$, i.e., $n = \Gamma(m)$. Taking logarithms, we get $\log n = \Theta(m\log m)$, and so $m = \Theta(\...
Yuval Filmus's user avatar
3 votes
Accepted

Why is a heap better than a linked list for implementation of a priority queue?

It only really matters in the limit: for small sizes, the difference isn't really important. But if you're doing a large number of each operation, $O(\log n) + O(\log n) = O(\log n)$ is ...
Draconis's user avatar
  • 7,138
3 votes
Accepted

Why do we need increase_key procedure in max priority queue?

In some algorithms, you'll be able to remember the index. In others, you might need a separate data structure (e.g., a hash table) that maps from the node to its index. When you insert a node into ...
D.W.'s user avatar
  • 161k
3 votes

How to classify simple priority queue algorithm

You can't prove an algorithm is correct without a specification what correctness means. This algorithm isn't a priority queue. A priority queue has two properties: pop always removes the highest-...
D.W.'s user avatar
  • 161k
3 votes

Queue that can sort by multiple priorities?

Simple solution: use two queues If you want to keep track of multiple priorities that are unrelated then you'll have to use 2 priority queues. You don't have to duplicate all the data, because you can ...
Johan's user avatar
  • 1,080
3 votes

Correct term for a priority queue with unique elements

I don't know of a name for the abstract data structure. There is a well-established implementation of what you describe, though: treaps, a combination of BST and heap (i.e. priority queue). This is ...
Raphael's user avatar
  • 72.6k
3 votes

Minimum time to finish all meetings

The problem is equivalent to job scheduling problem on parallel machines. The problem is $\mathsf{NP}$-hard even when the arrival time for each job/person is $0$ and the number of machines (or meeting ...
Inuyasha Yagami's user avatar
3 votes
Accepted

Designing a Queue that efficiently tracks position

One simple data structure is a balanced binary tree, with members stored in the leaves, and augmented so that each internal node also stores the number of leaves under it. Now you can implement all ...
D.W.'s user avatar
  • 161k
2 votes
Accepted

Leftist Tree initialization in O(n) time

The succession $a_i = 2^{-i}i$ is absolutely convergent. In more elementary terms: $$ \frac{n}{2} \le \sum_{i=1}^{\log n} \frac{ni}{2^i} \le n\sum_{i=1}^{\infty} \frac{i}{2^i} = n\sum_{j=1}^{\infty} ...
quicksort's user avatar
  • 4,272
2 votes
Accepted

How to classify simple priority queue algorithm

You asked about starvation. Starvation is impossible in your scheme: every item will eventually come off the queue, after finitely many dequeue operations. Consider an arbitrary priority-1 item, ...
D.W.'s user avatar
  • 161k
2 votes
Accepted

Implementing an efficent priority queue using only stacks

Unfortunately, it's not possible. The order you extract items from the stack depends only on the order they're pushed, regardless of the values in those items; a priority queue needs items to be ...
D.W.'s user avatar
  • 161k
2 votes
Accepted

Priority Queue Using Stack

Think about it. You can sort an array by adding all the items to a priority queue, then removing the items in sorted order. If you could run a priority queue in constant time, you could sort in ...
gnasher729's user avatar
  • 30.5k
2 votes
Accepted

Numerical Accuracy & Sorting Algorithms?

I'll give you a simple example. Suppose you have some floating-point numbers to add together. We'll assume they're all non-negative so that cancellation isn't an issue. For the purpose of this ...
Pseudonym's user avatar
  • 22.2k
2 votes

An algorithm to drop low-priority items from a heap-based priority queue

Let $n$ denote the size of the min-heap. It's easy to do this in linear time, i.e., $O(n)$ time: walk through the heap, copying over only the items that are below the threshold into an array; then ...
D.W.'s user avatar
  • 161k
2 votes

Priority queue with a buffer for delayed insertion and other tweaks

There are several approaches that combine multiple buckets and heaps to improve shortest path algorithms. At good starting point would be Dial's algorithm or Cherkassky, Goldberg & Silverstein.
Marcus Ritt's user avatar
2 votes
Accepted

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

Consider what will happen for the following graph. counterexample_graph = { 'U': {'V': 6, 'W': 7}, 'V': {'X': 10}, 'W': {'X': 1}, } Suppose ...
John L.'s user avatar
  • 39k
2 votes

Given n positive integers, pick two elements and subtract each by one with one operation. Find maximum number of operations

The goal is to make sure the one remaining element is as small as possible (if there is one). So as long as you reduce the 2 largest elements every step you will get to the lowest remaining element ...
Sean's user avatar
  • 21
2 votes

Given n positive integers, pick two elements and subtract each by one with one operation. Find maximum number of operations

Once we have played with the operations for a few times, we will soon realize that too large an element may not be able to pair with all other elements. So, while the end goal is to perform as many ...
John L.'s user avatar
  • 39k
2 votes

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

Since the operation "add 1 to all values greater than or equal to i" preserves order, you can augment a self balancing BST with this operation. While the particulars are dependent on how the ...
Command Master's user avatar
1 vote

Why can't we replace Dijkstra's priority queue with a regular queue?

The whole point of Dijkstra is that you visit the nodes in order of their distance from the source. If you use a queue that isn't a priority queue, then you visit the nodes in whatever "random" order ...
David Richerby's user avatar
1 vote

Short Fibonacci Heap

Corollary 1 in Fredman & Tarjan's paper states: A node of rank $k$ in an F-heap has at least $F_{k+2} \ge \phi^k$ descendants, including itself; where $F_k$ is the $k$th Fibonacci number ($...
Pseudonym's user avatar
  • 22.2k

Only top scored, non community-wiki answers of a minimum length are eligible