84
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)...
41
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 ...
37
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
$\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
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. ...
12
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 ...
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?
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 ...
7
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
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 ...
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
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 ...
6
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 ...
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" ...
6
$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 ...
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
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
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).
5
Let us denote the arrays by $A_1,\ldots,A_k$, their sizes by $|A_1|,\ldots,|A_k|$, their medians by $m_1,\ldots,m_k$, and their union by $\mathbf{A}$. We will try to solve the following more general problem: given $t$, determine the $t$'th smallest element in $\mathbf{A}$.
Let $m_r = \min(m_1,\ldots,m_k)$ and $m_s = \max(m_1,\ldots,m_k)$. Define
$$
N = \sum_{...
5
First note that $\text{increase-key}$ must be $O(\log n)$ if we wish for $\text{insert}$ and $\text{find-min}$ to stay $O(1)$ as they are in a Fibonacci heap.
If it weren't you'd be able to sort in $O(n)$ time by doing $n$ $\text{insert}$s, followed by repeatedly using $\text{find-min}$ to get the minimum and then $\text{increase-key}$ on the head by $\...
4
The main point is to do the analysis exactly without being sloppy. Let me define the depth of a node in this way. Depth of any leaf is 0 and depth of any non-leaf node is maximum depth among its children plus 1. One can note that
depth = $\log n - $ height.
Then for a particular node how much time does heapify take? By definition of depth you can see it is ...
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
Since nobody's really addressed heapSort yet:
Assuming you're using a max heap represented as an array and inserting your max elements backwards into your output array/into the back of your array if you're doing it in-place, the worst case input for heapSort is any input that forces you to "bubble down" or reheapify every time you remove an element. This ...
4
HeapSort: A procedure which sorts an array in place.
Can be in-place or not in-place, the point is it's using a heap data structure to help sort.
Building heap is linear with a careful analysis
See more here
4
If you mean the usual binary heap represented in an array, this is answered in "An Optimal Algorithm for Selection in a Min-Heap", by Frederickson. It is pretty complex.
Other priority queues have easier algorithms. For instance, if you use a threaded AVL tree as priority queue, you can just follow right neighbor pointers from the minimum value.
4
In the paper, $h_Q$ isn't the height. It's the length of a random walk away from the root in a full binary tree (they insist every leaf is "nil"), so the expression they have is the right thing.
Also, you can avoid induction. The probability of ending at a specific leaf of depth $d$ is just $2^{-d}$. So the expected length of the walk is
$$
\sum_{\ell\...
4
Binary heaps are one possible implementations for priority queues. Although their operations are best understood as binary trees, their implementation as arrays is essential. They are stored efficiently, due to the perfect balance you mention, and do not need explicit pointers to children or parent (as these are found by calculating their index in the array)....
4
Please note that $ m \leq n(n-1)/2 $, thus $m/n < n/2$. So the example $m=3, n=1$ does not happen.
First, the article clearly claims that this improvement is achieved whenever $ m $ is larger than $ n $,
By using a $d$-ary heap with $d = m/n$, ..., an improvement over the O(m
log n) running time of binary heap versions of these algorithms
whenever ...
4
You could argue that the level-hierarchy gives more information, but not by much. Assuming a full max-heap of distinct values the $min$ element is on the deepest level of $\frac{n+1}{2}$ nodes. Unless there is some additional ordering to the heap, it would then take $\Omega(n)$ just to find the $min$ element.
Only top voted, non community-wiki answers of a minimum length are eligible