# Questions tagged [priority-queues]

The tag has no usage guidance.

59 questions
Filter by
Sorted by
Tagged with
23 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 ...
81 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 ...
22 views

111 views

### “Minimum Stack”

I am now preparing for a test in my algorithms course and I have stumbled upon a question about a data structure which seems too trivial for me, but is probably not trivial at all. The question is: ...
2k views

### Priority queue with unique elements and sublinear time merge?

Some priority queues, like the height-based leftist tree (or here) support merging in $\mathcal O\left(\log n\right)$ time. I am looking for a priority queue that merges in (expected|average|...
952 views

### Which priority queue implementations are stable?

I can't answer this question. It seems simple but I really don't know how to approach it. Here it is: A priority queue is said to be stable if deletions of items with equal priority value occur in ...
32k views

### Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list

Most probably, this question is asked before. It's from CLRS (2nd Ed) problem 6.5-8 -- Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total ...
I'm looking for a data structure that can work as a priority queue with reasonable maintenance complexities (like $O(\log n)$ for insertion and deletion) and that has a theoretical unbounded limit for ...
I have recently learned about various randomized algorithms for load balancing. The model is always that there are $m$ balls and $n$ bins and the balls arrive one at a time. The task is to minimize ...