29
votes
Accepted
What is the advantage of heaps over sorted arrays?
$\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 ...
- 766
15
votes
Accepted
Why use heap over red-black tree?
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 ...
- 291
8
votes
Accepted
Why can't we sort an Array in O(n) using Fibonacci Heap?
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?
- 21.6k
6
votes
Accepted
Why clear the child's and not the parent's mark in Fibonacci heaps?
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 ...
- 21.6k
6
votes
What is the advantage of heaps over sorted arrays?
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 ...
- 28.3k
6
votes
What is the time complexity for getting the size of a heap?
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,931
6
votes
Is there a name for this priority queue data structure?
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" ...
- 1,003
6
votes
Accepted
What are the disadvantages of Fibonacci Heaps?
$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 ...
- 1,028
6
votes
If both could be implemented with the other, what are the differences between priority queues and binary heaps?
Based on standard usage of the terms, a heap is a specific data structure, with a specific representation in memory. A priority queue is an abstract data type: it identifies some operations that must ...
D.W.♦
- 156k
5
votes
Accepted
Why do you need to fill the first element of array when implementing heap?
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 ...
- 9,425
5
votes
Best and worse case inputs for heap sort and quick sort?
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 ...
- 51
5
votes
Proving that an $n$-element heap has at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes
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/...
5
votes
To find median of $k$ sorted arrays of $n$ elements each in less than $O(nk\log k)$
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 ...
- 275k
5
votes
Why is Binary Heap never unbalanced?
You must refer to the definition of a Binary Heap:
A Binary heap is by definition a complete binary tree ,that is, all levels ...
- 1,195
5
votes
Accepted
Min Fibonacci Heap - increase key
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 $...
- 12.7k
4
votes
Finding the $k$-smallest elements in a min-heap
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 ...
- 3,310
4
votes
Accepted
Randomized Meldable Heap - Expected Height
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.
...
- 2,916
4
votes
Is it possible to build a heap from the root to the leaves?
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 ...
- 29.8k
4
votes
Ideal value of d in a d-ary heap for Dijkstra's algorithm
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 ...
- 1,934
4
votes
Accepted
Amortised analysis of binary heap insert and delete-min
First, for a bit of clarifying terminology: rather than proving an amortized insertion cost of $O(\lg n)$ and an amortized deletion cost of $O(1)$, you are using those amortized costs to prove ...
4
votes
What is the time complexity for getting the size of a heap?
Depends on how you implement your ADT heap. You can expand size as a counter of next operations. In that manner, if you are ...
- 507
4
votes
Accepted
Proving that converting min-heaps to max-heaps requires time Ω(n)
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 ...
- 4,431
4
votes
Heap structure in array, computing parent and child
While it is possible to write a formal proof, I think the best proof is by picture:
If you still want a formal proof, here it is. We start by noting that level $d$ of the tree (counting from 0) ...
- 275k
4
votes
Accepted
heap pop creates unbalanced tree?
When popping the root, it is first replaced by the very last element, and then a heapify operation is performed to maintain the heap invariant, namely, that every node is smaller than its children.
...
- 275k
4
votes
An algorithm to efficiently insert a list of elements into a binary heap ("bulk insertion")
Wikipedia describes a procedure, due to Floyd, which constructs a heap from an array in linear time.
It also mentions a procedure for merging two heaps, of sizes $n$ and $k$, in time $O(k + \log k \...
- 275k
4
votes
Number of possible min heaps
The flaw in your approach is that you assume that the second level contains only $2$ and $3$. The following examples is min heap with $3$ not in the second level.
...
4
votes
Why is Binary Heap never unbalanced?
The question is a little confusing, since a binary heap is usually implemented in an array, not a tree. The tree is used for visualization.
Consider the following heap:
It is given by the following ...
- 1,659
4
votes
Why is heap insert O(logN) instead O(n) when you use an array?
Given your link, you seem to be interested in data structures supporting the following operations:
Create(m): create a new instance with room for m elements.
Size(): return the number of elements ...
- 275k
4
votes
Accepted
Find the smallest difference between two numbers in a DS in O(1) time
Use an AVL tree with each node having three additional entries $\min,\; \max$, and $\text{closest_pair} = (i,j)$, representing the minimum and maximum values of the tree rooted at that node. At the ...
- 298
3
votes
Can a heap have no elements?
It's up to you to decide. It's a pathological case which is quite similar to the empty graph (on zero vertices) — sometimes it makes sense to admit it, and sometimes not. It depends on the ...
- 275k
Only top scored, non community-wiki answers of a minimum length are eligible