Hot answers tagged

91 votes
Accepted

What's the difference between a binary search tree and a binary heap?

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 ...
user avatar
  • 1,092
49 votes

What's the difference between a binary search tree and a binary heap?

Summary ...
user avatar
37 votes

What's the difference between a binary search tree and a binary heap?

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. ...
user avatar
  • 1,711
27 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 ...
user avatar
14 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 ...
user avatar
  • 281
13 votes

What's the difference between a binary search tree and a binary heap?

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 ...
user avatar
  • 27.6k
8 votes

Searching through a heap complexity

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 ...
user avatar
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?
user avatar
  • 18.9k
7 votes
Accepted

Heap-like data structure allowing peek at largest & smallest

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(...
user avatar
  • 141k
7 votes

Extract Max for a max-heap in $\log n + \log\log n$ comparisons

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 ...
user avatar
  • 406
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 ...
user avatar
  • 18.9k
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 ...
user avatar
  • 25.2k
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).
user avatar
  • 5,900
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" ...
user avatar
  • 983
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 ...
user avatar
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 ...
user avatar
  • 141k
5 votes
Accepted

Merging Sorted lists using Heap Data Structure

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 ...
user avatar
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 ...
user avatar
  • 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/...
user avatar
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 ...
user avatar
  • 9,325
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 ...
user avatar
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 ...
user avatar
  • 1,135
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 $...
user avatar
  • 12.3k
4 votes
Accepted

Show that the running time of the build_heap function is $O(n)$

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 ...
user avatar
4 votes
Accepted

Can we create binomial heaps in linear time?

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, ...
user avatar
4 votes

Build-Max-Heap vs. HeapSort

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 ...
user avatar
  • 291
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 ...
user avatar
  • 3,200
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. ...
user avatar
  • 2,886
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 ...
user avatar
  • 27.6k
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 ...
user avatar
  • 1,914

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