# Questions tagged [heaps]

The tag has no usage guidance.

178 questions
Filter by
Sorted by
Tagged with
111k views

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

These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?
430 views

### Min-Heap Insertion Problem

I try to insert 4-9-3-7 and 1 (left to right) into a Min-Heap (using array implementation). Then 5 times Remove Smallest Number from this Min-Heap. how many swap between two elements in array occurred?...
230 views

### Binary heap of size $n$ splitting to 2 heaps of size $n/2$ [closed]

Input: A binary heap of size $n$. $n$ is even. Output: 2 binary heaps of size $n/2$ each. I found this question in a solved algorithms test and the solution said: "There is no better solution than to ...
70 views

### Binomial heap multiplying nodes

Input: A max binomial heap $H$, and a pointer to a node $V$. Output: A max binomial heap, where all the children of $V$ are multiplied by 2. I have tried solving this by taking out the node $V$ ...
140 views

### Binary heap removal peculiar potential function analysis [closed]

Given the potential function $\phi$, it seems that remove max may take $O(1)$ amoratized, meaning that $n$ removals would take $O(n)$, which can't be, as it means we get a linear time comparison based ...
326 views

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

Given the following two functions, prove that the build_heap function, which transforms an array A into a max-heap-sorted array A' runs in $O(n)$. ...
561 views

408 views

### MinHeap represented by an array - two simple statements

I'm trying to prove/disprove two statements. I just want to make sure with you I'm on the right line. These are the following statements: Preface : Let A[n] be an array of min-heap (a min-heap ...
680 views

### Input that causes an operation on a binomial heap to run in $\Omega(\log n)$ time?

I was studying binomial heaps and its time analysis. Are there any inputs that cause DELETE-MIN, DECREASE-KEY, and DELETE to run in $\Omega(\log n)$ time for a binomial heap rather than $O(\log n)$?
6k views

### Potential function binary heap extract max O(1)

I need help figuring the potential function for a max heap so that extract max is completed in $O(1)$ amortised time. I should add that I do not have a good understanding of the potential method. I ...
3k views

### What is the purpose of Mark field in Fibonacci Heaps?

In Fibonacci heaps, we keep a mark field for every node in the heap. Initially all the nodes are unmarked. Once a node is deleted, its parent is marked. If a node is deleted and its parent is already ...
1k views

### Determine whether the $k^{th}$ smallest element in max-heap is greater than a given number

A set of numbers is stored in a max-heap. We want to find an algorithm with $O(k)$ time complexity to check if $k^{th}$ smallest element is greater than an arbitrary given number.
21k views

### Deletion in min/max heaps

I think I'm confused about deletion in heaps, and since I have an exam today, I'm looking for your help to correct me. I will post photos since it will makes it a bit more clear. Note(forget about ...
4k views