# Tag Info

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 ...
• 22.2k
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 ...
• 72.6k

### 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" ...
• 1,043
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 ...
• 1,073

### 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 ...
• 161k

### 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 ...
• 30.5k
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 ...
• 278k

### 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 ...
• 419
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 ...
• 3,098