# Tag Info

27

Our idea is to use threaded splay trees. Other than the Wikipedia article we will thread the trees so that every node has a pointer next to its successor in the in-order traversal; we also hold a pointer start to the smallest element in the tree. It is easy to see that extracting the smallest element is possible in (worst case) time $\mathcal{O}(1)$: just ...

20

Insert: $\mathcal{O}(\log n)$ Get-Min: $\mathcal{O}(1)$ Extract-Min: $\mathcal{O}(1)$ Amortized Time Simple implementations of a priority queue (e.g. any balanced BST, or the standard binary min-heap) can achieve these (amortized) running times by simply charging the cost of Extract-Min to insert, and maintaining a pointer to the minimum element. For ...

14

2-4 trees have amortized $O(1)$ modifications at known locations. That is to say, if you have a pointer to some location in the tree, you can remove or add an element there in $O(1)$ amortized time. You can thus just keep a pointer to the minimum element and the root node in a 2-4 tree. Inserts should go through the root node. Updating the pointer to the ...

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....

10

Assume you have a priority queue that has $O(1)$ find-min, increase-key, and insert. Then the following is a sorting algorithm that takes $O(n)$ time: vector<T> fast_sort(const vector<T> & in) { vector<T> ans; pq<T> out; for (auto x : in) { out.insert(x); } for(auto x : in) { ans.push_back(*out.find_min()); ...

8

By request, here is the structure I found after I formulated the question: The basic idea is to use a threaded Scapegoat tree along with a pointer to the minimum (and for good measure, the maximum as well). A simpler alternative to threading is maintaining predecessor and successor pointers in every node (which is equivalent, simpler, but has more overhead)....

8

Yes, it can be done in amortized O(1) time (enqueue, dequeue, minimum). Have a look at the code and explanation given here. Here are the most relevant parts quoted from the above link (emphasis mine; and of course, all credits for the solution go to the original author, Keith Schwarz): A FIFO queue class that supports amortized O(1) enqueue, dequeue, and ...

8

The reason that your operation is not listed, is that one is not simply interested in all operations that can be easily implemented using a certain data structure, but rather the other way. Given a set of operations, what is the most efficient way (in terms of space and time) to implement these operations. (But I add more to this later) Binary heaps ...

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

The algorithm you suggest is simply heapify. And indeed - if you increase the value of an element in a min-heap, and then heapify its subtree, then you will end up with a legal min-heap.

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

If $P$ is the number of processing units available, consider $P$-ary heaps¹. When descending to perform some operation on a set of keys, you can fork whenever keys lead to different children. If the heap is balanced, this results in independent taks for a uniformly chosen set of keys (and sufficiently big $n$) after having descended a constant number of ...

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

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 ...

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

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 ...

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

When returning the min element, I assume you also want to remove it from the data structure? Otherwise it's trivial to just always keep track of the least element when you alter the data structures via any of the other operations. I'm not entirely sure how much cheating you allow, but you could keep two additional queues, such that on insertion to your ...

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

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

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

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.

2

A soft heap is a subtle modification of a binomial queue. The data structure is approximate with an error parameter $\epsilon$. It supports insert, delete, meld and findmin. The amortized complexity of each operation is $O(1)$, except for insert which takes $\log (1/\epsilon)$ time. The novelty of the soft heap is in beating the logarithmic bound on the ...

2

Okay, finally got you the complexity you were looking for, and what's best, I found it in the literature: Worst-Case Complexity Delete: $\bf\mathcal{O}(1)$ Delete-min: $\bf\mathcal{O}(1)$ Find-min: $\bf\mathcal{O}(1)$ Insert: $\bf\mathcal{O}(log\ n)$ Reference IF MELD is allowed to take linear time it is possible to support DELETE-MIN in worst case ...

2

Approaching this problem by maintaining two data-structures: an Array and a Binary Tree. To maintain indexing in the array, previously you'd have the $\Omega(\dfrac{\log n}{\log\log n})$ bound; but more recently this has been overcome by modifying the analysis from the chronogram technique. The new [lower] $\Omega(\log n)$ bound has been proved for similar ...

2

Like with anything in CS, there is no "best something". There are always trade offs. But, perhaps this section of Wikipedia's article on Fibonacci heap could help you: Fibonacci heap: Amortized $\mathcal{O}(\log\ n)$ delete and delete_min, amortized $\mathcal{O}(1)$ decrease_key and $\mathcal{O}(1)$ the rest. Brodal queue: Worst-case $\mathcal{O}(\log\ n)$ ...

2

Worst-case complexity Insert: $\mathcal{O}(1)$ Find-min: $\mathcal{O}(1)$ Decrease-key: $\mathcal{O}(1)$ Delete: $\mathcal{O}(\log \log n)$ Space: $\mathcal{O}(n)$ Proof THEOREM 1. We can implement a priority queue that with n integer keys in the range $[0 , N )$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in ...

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