# Tag Info

## Hot answers tagged heaps

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 ...
• 796
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
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?
• 22.3k

### 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,951

### 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 ...
• 30.7k

### 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,043
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,073

### 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 ...
• 162k

### 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
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,465

### 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 ...
• 278k

### 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,215
Accepted

• 278k

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

### 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,669

### 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 ...
• 278k
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 ...
It isn't, neither from a complexity nor from a correctness point of view, however, by starting the counter at $n$ you are doing useless work. Heapify is a procedure that, if invoked on a node $v$ ...