# Tag Info

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

Summary ...

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

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

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

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

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

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