The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
13 views

Creating an algorithm with a certain worse case runtime [duplicate]

The inputs are x sorted lists (in increasing order) and in each list there are j/x elements (we are assured the numbers will work out to be a natural number. eg: j = 9, x = 3 L1 = [1, 2, 5], L2 = ...
0
votes
2answers
129 views

How to calculate probability of packet loss and drop rate?

In a queuing system (M/M/1) with a finite packet capacity $z$, how do you determine the probability of packet loss if we assume that packets are dropped when the system is full? Packets arrive with a ...
1
vote
0answers
55 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 ...
0
votes
1answer
51 views

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

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 $\mathcal{O}(n)$ because you will have to go through each and ...
0
votes
0answers
70 views

Dynamically weighted priority queue?

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
64 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
55 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
260 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
55 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
409 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
284 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 ...
2
votes
2answers
8k 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
219 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
436 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
74 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
8k 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
337 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
131 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
653 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
275 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
281 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() : ...
29
votes
9answers
4k 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: ...