72
Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you want sorted elements, go with BST.by Dante is not a geek
Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)). Insert is O(logN)...
36
Summary
Type BST (*) Heap
Insert average log(n) 1
Insert worst log(n) log(n) or n (***)
Find any worst log(n) n
Find max worst 1 (**) 1
Create worst n log(n) n
Delete worst log(n) log(n)
All average times on this table are the same as their worst times except for Insert.
*: everywhere in ...
35
Both binary search trees and binary heaps are tree-based data structures.
Heaps require the nodes to have a priority over their children. In a max heap, each node's children must be less than itself. This is the opposite for a min heap:
Binary search trees (BST) follow a specific ordering (pre-order, in-order, post-order) among sibling nodes. The tree must ...
23
I did not find a closed form, but according to this entry in the Online Encyclopedia of Integer Sequences the sequence starts with
1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ...
You can find a not-so-nice recursion in the OEIS database. Basically the idea ...
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 ...
14
$\small \texttt{find-min}$ (resp. $\small \texttt{find-max}$), $\small \texttt{delete-min}$ (resp. $\small \texttt{delete-max}$) and $\small \texttt{insert}$ are the three most important operations of a min-heap (resp. max-heap), and they usually have complexity of $\small \mathcal{O}(1)$, $\small \mathcal{O}(\log n)$ and $\small \mathcal{O}(\log n)$ ...
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....
13
Try the following:
The weight $w_i$ of an element $i$ in the heap $H$ is its depth in the corresponding binary tree. So the element in the root has weight zero, its two children have weight 1 and so on. The you define as potential function
$$\Phi(H)=\sum_{i\in H}2 w_i.$$
Let us now analyze the heap operations. For insert you add a new element add depth $...
13
With data structure one has to distinguish levels of concern.
The abstract data structures (objects stored, their operations) in this question are different. One implements a priority queue, the other a set. A priority queue is not interested in finding an arbitrary element, only the one with largest priority.
The concrete implementation of the structures. ...
11
Actually it depends on your point of view, or level of detail.
The heap, or better priority queue, as abstract data structure usually supports operations like is-empty, add-element, delete-min. And usually not find-element. This is the data structure seen as a specification, fixing the set of operations and their behaviour. The implementation is unknown, it ...
10
It does change the complexity of the operations. Simply speaking, the root list $W$ gets too large.
We have two expensive operations, which are ExtractMin and DecreaseKey. Remember that the amortized analyisis uses the potential function
$$ \Phi(F)=|W| +2\cdot \text{# marks}. $$
If we call ExtractMin this might costs $O(|W|)$, however after the operation, ...
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
Increase-key is not a $O(1)$ operation on Fibonacci heaps. You're thinking of decrease-key.
Exercise: Why can't increase-key be a $O(1)$ operation on this data structure?
8
Its about pragmatic efficiency.
The big-O notation tends to simplify many aspects of the machine that the algorithm is executing on. It leaves out the constant multipliers, and constant additions. It doesn't address that even those operations take variable amounts of time. Nor does it address the fact that implementations do not have an infinite/very very ...
7
I assume that the operation build just turns an array into a heap by repairing the heap-property for every subtree bottom-up (let the operation for a single repair step called heapify).
It is not so hard to see, that heapify takes $O(h)$ steps, where $h$ is the height of the subtree to repair. We set $k=\lfloor \log n \rfloor $ as the height of heap. ...
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
Explanation for log n + log log n comparisons:
1) First, remove the max element from the heap, leaving a hole at the root.
2) Next, remove the last element of the heap (at the bottom right), and hold it in a temp.
3) Reconstruct the heap by iteratively replacing the hole with the greater of its 2 children. This loop takes log n comparisons (comparing the ...
6
There's no need to bubble-up the element all the way to the root. You can replace the item to be removed with the last element in the heap. If that new element is less than its parent, then bubble it up. If it's greater than its children, bubble it down.
I implemented this in my DevSource article, A Priority Queue Implementation in C#. Full source is ...
6
You are correct: it's $\Theta(n)$ in the worst case. Suppose you're looking for something that's no bigger than the smallest value in a max-heap. The max-heap property (that the value of every node is at least as big as everything in the subtree below it) gives you no useful information and you must check both subtrees of every node.
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
heap- Since the best and worst case are the same does it not matter the input order? The number of comparisons and assignments will always be the same? I imagine in a heap sort it may be the same since the real work is done in the insertion, but the sorting only uses the removal of the max/min heap? Is that why?
The number of comparisons made actually can ...
5
A min-heap typically only supports a delete-min operation, not an arbitrary delete(x) operation. I would implement delete(x) as a composition of decrease-key(x, $-\infty$), and delete-min. Recall, that to implement decrease-key, you would bubble up the element to maintain the heap property (in this case all the way to the root). In a binary heap, to ...
5
Elmasry et al. discuss reducing the number of comparisons for extract-max to $\log n + o(\log n)$ in "A Framework for Speeding Up Priority-Queue Operations". See also Elmasri's "Layered Heaps", Edelkamp et al.'s "Two Constant-Factor-Optimal Realizations of Adaptive Heapsort", Carlsson's "An optimal algorithm for deleting the root of a heap", and Gonnet and ...
5
Hint: Try to merge the lists in the correct way, using the fact that merging lists of size $m_1,m_2$ costs $O(m_1+m_2)$. If you do this correctly, you will obtain an $O(n\log\log n)$ algorithm.
We can also get a matching lower bound. The number of possible answers is
$$
\begin{align*}
\frac{n!}{(n/\log n)!^{\log n}} &\sim
\frac{\sqrt{2\pi n}(n/e)^n}{\...
5
To understand Fibonacci heaps, it may help to understand binomial heaps first.
A binomial heap is a forest of heap-ordered binomial trees. A binomial tree of degree k is a node whose children are binomial trees of degree k-1, k-2, ... 0. Note that the number of nodes in a binomial tree of degree k is $2^k$.
If you never do any decrease key operations (or ...
5
Probably, you mean this:
A heap of size $n$ has at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes with height $h$.
Proof can be found for example here:
http://www.cs.sfu.ca/CourseCentral/307/petra/2009/SLN_2.pdf
5
It is not some magic element but $-\infty$, which is because this is min-heap, in max-heap it would be $\infty$.
The sole purpose is consistent representation of all elements inserted - it guarantees that the next element can be compared and it will be smaller (or bigger - for appropriate heap type) - just to avoid checking whether inserted element is the ...
5
To answer your questions, you have to define which different actions you will perform and how often, and you have to evaluate the time complexity of each action.
Which method is performing better overall will depend on the individual complexities and how often each action is performed.
Sorting an array has a very high time complexity; heap operations are ...
5
If you're talking about an ADT, you can't really say. It depends on the implementation. You can certainly do it in O(1) (for example by keeping a counter).
Only top voted, non community-wiki answers of a minimum length are eligible
