# Tag Info

14

The purpose of the heap is to give you the minimum, so I'm not sure what the purpose of this for-loop is - for j := 2 to k. My take on the pseudo-code: lists[k][?] // input lists c = 0 // index in result result[n] // output heap[k] // stores index and applicable list and uses list value for comparison // if ...

13

First of all, I think that your assumption of all lists having $n/k$ entries is not valid if the running time of the algorithm depends on the length of the longest list. As for your problem, the following algorithm should do the trick: Put the first elements of the lists in a min-heap $H$ of size $k$. Remember for each element the list $l_m$ it belongs to....

11

Good question. One of the important applications of the data structure PriorityQueue is in Dijkstra's algorithm. Each node gets a distance from the initial node, which is updated when shorter paths are discovered. Hence updates only change the key in one direction. The problem in the implementation of DecreaseKey is not that it is only decreasing (rather ...

8

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 gives you constant-time access to the first and last element, respectively, and maintaining the threading takes only constant-time overhead for each dictionary ...

7

One simple approach is to use a max-heap. Separately keep track of the minimum element stored in the heap. Then all operations can be done relatively efficiently: Load from array can be done in $O(n)$ time, building Build-Heap. Each of the peek operations takes $O(1)$ time. Decreasing the maximum element can be done in $O(\lg n)$ time. You decrease it ...

6

It takes $\Omega(n)$ time to find the median of a heap in the worst case. The reason is that the lowest levels of the heap (the leaves and their close ancestors) can be very disordered, and they make up the majority of the heap. As a result, if you can find the median on a heap, you can find a median of the $\Omega(n)$ unordered elements near the leaves. ...

6

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" queries on ranges You can support fast update queries on ranges, for some combinations of updates and queries The $j$th node at height $k$ in the tree "summarizes" ...

5

$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 section named "Practical considerations": Fibonacci heaps have a reputation for being slow in practice due to large memory consumption per node and ...

4

Wikipedia claims that insertion takes $O(1)$ amortized time, and so converting an array of numbers into a binomial heap should indeed take time $O(n)$. This is also supported by these lecture notes, and probably mentioned in CLRS.

4

Keep your elements in linked lists of buckets. Buckets will have size $O(\lg^2 n)$ when stored in a list with $n$ total elements. Buckets are stored as balanced search trees with $O(\lg n)$ insert (and, since each bucket has size $O(\lg^2 n)$, this is actually $O(\lg \lg n)$), $O(1)$ extractMin, $O(n+m)$ merge, $O(\lg n)$ split, and no duplicates. The liked ...

4

I don't understand your claim that a traditional heap is too costly to augment. If the heap is currently of size $N$ and the $N+1$st element is inserted, allocate a new array of size $2N$ and copy the old heap into its prefix. This takes amortized constant time. You can also shrink the heap in this way, for example if it is only half full you can shrink it ...

3

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 the priority queue, you also add it to that mapping. When you need to know a node's index (e.g.,to call increase_key), you look it up in that mapping.

3

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-priority item; and it resolves ties (in priority) in a FIFO fashion. Your algorithm doesn't do that; if the first 20 items in the last are all low priority, but ...

3

The exercise wants you to use a priority queue (also known as a heap). I'll let you figure out how this helps. If the input were integral, then you could do even better by sorting the list. This might still work even in the general case, but requires more work. (You might need to sort both the values themselves and their fractional parts.)

3

Although the exact problem posed in the original question does seem to be difficult (and I would be interested in a solution to that problem, especially the infima finding part). I just wanted to note that if the partially ordered set indeed consists of vectors using a product order, and if it is sufficient to just have the guarantee that the priority queue ...

3

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 just put a reference (pointer) to the data in your queue. That way you only have 1 location where your object resides and two pointers to it in the two ...

3

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 asymptotically faster than $O(n) + O(1) = O(n)$.

3

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(\frac{\log n}{\log\log n})$. In other words, $$\Gamma^{-1}(n) = \Theta \left( \frac{\log n}{\log \log n} \right).$$ Therefore your running times, which are ...

2

You are correct that using a priority queue is a good idea. It doesn't give an optimal answer though. (Assuming that what you are trying to optimize is the time that the last processor finishes executing the last job.) This scheduling problem is NP-complete, and the priority queue based method gives an answer that is within a factor of 2 of optimal. See, ...

2

Here's how I would suggest that you approach the problem. Try running each data structure by hand on some small examples. Then, based on those examples, see if you can form any conjecture about which data structures are stable and which ones aren't. For the ones you suspect are stable, try proving it. For the ones that you suspect are not stable, try to ...

2

It depends on the structure of your heap. You can create a heap based around the median being the first element, but in a typical min or max heap, it's going to be O(n). Check this post: https://stackoverflow.com/questions/2579912/how-do-i-find-the-median-of-numbers-in-linear-time-using-heaps

2

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 with priority and value/key being different things, though. If priority and value are the same, use any priority queue and add uniqueness, i.e. by combining it ...

2

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} \left( \frac{1}{2^j}\sum_{i=1}^{\infty} \frac{1}{2^i} \right) = 2n$$

2

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, call it T. I'll prove that T will eventually be removed from the queue. Let $M$ denote the number of items that are older than T (i.e., were enqueued before T). ...

2

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 call MakeHeap to turn it into a heap. I would be surprised if you can do better than this, in asymptotic worst-case running time. For instance, any approach ...

2

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.

2

2

You are right. Checking k < d[u] is not sufficient and updating d[u] on the next line is not necessary. The check prevents proceeding when the source is picked up from the queue (then k = 0 and d[s] = 0). Also, d[u] (u is fixed) is monotonically decreasing as loop proceeds, so even though it is updated after (u, d[u]) is put on the queue, k >= d[u] ...

2

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 example, I'm going to use decimal with four significant digits of precision just to illustrate the point. The numbers are: 1.000e-4 1.000e-4 1.000e-4 1.000e-4 1....

2

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 linear time. But you can't.

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