The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
24 views

Where To Put Duplicates in Max Heap?

Question: Suppose you have a list of integers and it might contain duplicates. Build a Max Heap using this list. Where would the duplicates of the max integer reside in this Max Heap data ...
1
vote
1answer
21 views

What will trigger a worst time search for a binary heap and what is the run time?

I thought if the values in a max or min heap is monotonically increasing or decreasing, then this will trigger a worst case run time of O(n) because you will have to go through each and every single ...
-1
votes
0answers
31 views

Dynamically weighted priority queue? [closed]

Elements are stored in a single dynamic data-structure $D$ Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$ The function $f$ is weighting based on the value ...
4
votes
0answers
51 views

Concurrent priority queue with lazy increase-key

I could use a priority queue supporting the find-and-delete-min, and lazy-increase-key operations. The last term is my ...
0
votes
0answers
43 views

Amortized analysis of nested loop

I have a fairly simple algorithm, consisting of an inner while-loop in an outer for-loop. Even though the algorithm is simple enough, it's quite hard to explain exactly what it does. However, it's ...
2
votes
1answer
198 views

Can we create binomial heaps in linear time?

I'm studying binomial heaps in anticipation for my finals and the CLRS book tells me that insertion in a binomial heap takes $\Theta(\log n)$ time. So given an array of numbers it would take ...
1
vote
2answers
50 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: ...
3
votes
2answers
339 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 ...
0
votes
1answer
237 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 ...
1
vote
2answers
6k 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 ...
1
vote
3answers
192 views

Priority queue with ubounded number of elements (i.e., with dynamic storage)

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 ...
1
vote
1answer
365 views

Load balancing. Why not use priority queues?

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 ...
2
votes
1answer
73 views

performance between the data structures

I have developed two existing data structures and I want to see their performances over a certain algorithm. In this case I use Dijkstra's algorithm with binary and Fibonacci heaps. Just to ask, if I ...
7
votes
3answers
6k 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 ...
13
votes
6answers
312 views

Priority queue for partially ordered priorities with infima

I have a some objects with priority that is compound type and is only partially ordered. I need to select the objects in order of this priority (i.e. yield minimal item each time). But rather than ...
1
vote
2answers
111 views

Using Queues for a Stack and Stacks for a Queue

I was asked a question on how to use a pair of Queues to create a Stack and how to use a pair of Stacks to create a Queue. Any thoughts on how I would do this? Right now I don't even know where to ...
4
votes
2answers
516 views

Lower bounds: queues that return their min elements in $O(1)$ time

First, consider this simple problem --- design a data structure of comparable elements that behaves just like a stack (in particular, push(), pop() and top() take constant time), but can also return ...
4
votes
1answer
265 views

Batch processing in increase-key function using binary heap

Is there an algorithm to perform batch processing in the increase-key operation? Let us say, a binary heap (min-heap) is used. In the normal increase-key function, if we perform increase key on one ...
2
votes
5answers
1k views

Most efficient known priority queue for inserts

In terms of asymptotic space and time complexity, what is the most efficient priority-queue? Specifically I am looking for priority queues which minimize the complexity of inserts, it's ok if deletes ...
2
votes
0answers
263 views

Queue that can sort by multiple priorities?

I have a high interest in priority-queues (E.g., see my answers on: Does there exist a priority queue with $O(1)$ extracts?), and was wondering if there is a priority-queue or similar data-structure ...
10
votes
1answer
1k views

Priority queue with both decrease-key and increase-key operations

A Fibonnaci Heap supports the following operations: insert(key, data) : adds a new element to the data structure find-min() : ...
27
votes
9answers
3k views

Does there exist a priority queue with $O(1)$ extracts?

There are a great many data structures that implement the priority-queue interface: Insert: insert an element into the structure Get-Min: return the smallest element in the structure Extract-Min: ...