# Questions tagged [heaps]

The tag has no usage guidance.

175 questions
Filter by
Sorted by
Tagged with
110k 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?
7k views

### How many different max-heaps exist for a list of n integers?

How many different max-heaps exist for a list of $n$ integers? Example: list [1, 2, 3, 4] The max-heap can be either 4 3 2 1: ...
37k views

### Increase-key and decrease-key in a binary min-heap

In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally ...
29k views

### Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list

Most probably, this question is asked before. It's from CLRS (2nd Ed) problem 6.5-8 -- Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total ...
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 ...
182 views

### Randomized Meldable Heap - Expected Height

Randomized Meldable Heaps have an operation "meld", which we then use to define all other operations, including insert. The question is, what is an expected height of that tree with $n$ nodes? ...
9k views

### What is the advantage of heaps over sorted arrays?

I'm fairly new to heaps and am trying to wrap my head around why min and max heaps are represented as trees when a sorted array appears to both provide min / max properties by default. And a follow ...
231 views

559 views

### Why use heap over red-black tree?

Heap supports insert operation in $O(\log n)$ time. And while heap supports remove min/max in $O(\log n)$ time, to remove any element (non min/max) heap takes $O(n)$ time. However, red-black tree ...
177 views

### An algorithm to efficiently insert a list of elements into a binary heap (“bulk insertion”)

I wonder if there is any elegant algorithm for inserting a list of elements into a binary heap (at once) whose performance would be close to that of inserting elements one by one when there are only a ...
2k views

### Build-Max-Heap: Why Start i at floor(A.length/2) rather than A.length?

Taken from CLRS third edition, a procedure is given for Build-Max-Heap ...
157 views

### Min Fibonacci Heap - increase key

I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement increase-key operations for min-heaps....
4k views

### Heapsort for sorted input

What is the running time of heapsort when the input array is in increasing order? How about decreasing order? (I came across these questions in CLRS.) Here is what I have done so far ... For the ...
486 views

### When two siblings in a heap are equal, how do you bubble down?

I have a heap where both child nodes of the root are 10, and I'd like to perform an operation to remove the min value 9. I proceed to replacing the root with its next of kin, 18. However when I ...
169 views

### If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index?

If we store a min heap of $n$ elements, $\color{Blue}{[1,2, \dots n]}$ into an array, then what can be minimum value present at any index $i$ and maximum value present at any index $i$. (elements are ...
261 views

### Concurrent priority queue with lazy increase-key

I could use a priority queue supporting the find-and-delete-min, and lazy-increase-key operations. The last term is my "...
618 views

### Building a tree with the heap property from an array and preserving its order

How efficiently can I build a binary tree satisfying the heap property from an array and such that the inorder traversal of the tree is the original array? For example, if I have: 2 1 5 6 2 3 I ...
4k views

64 views

### Returning sorted lowest k elements in a binary heap

Given a binary heap of size $n$ and a number $k\le n$. How can I return an array with size $k$, which contains the $k$ lowest elements in the binary heap, so that it will be sorted in the end? The ...
132 views

### Complexity of forming a min heap out of a given array with k inversions

If a given heap has $k$ inversions, what is the complexity of making it into a valid min heap? We could define an inversion as a tuple (node, descendant), where the node has a key value strictly ...
635 views

### Heap structure in array, computing parent and child

I am studying data structures from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, and in the section of heapsort it talks about a data structure beneath the algorithm : a heap, ...
109 views

### Proving that converting min-heaps to max-heaps requires time Ω(n)

Suppose I have a min-heap SH stored inside an array. I can perform the operations: view-min(SH) in $O(1)$ extract-min(SH) in $O(\log n)$ insert(SH) in $O(\log n)$ is-empty(SH) in $O(1)$ If I want to ...
2k views

### Amortised analysis of binary heap insert and delete-min

I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function. We can assume, that insert is O(logn) and delete-min is O(logn) too. The goal is ...
91 views

### How to come up the number of nodes on a given level in heaps?

CLRS asked it's readers to prove that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$ in any n-element heap as an exercise. The principle of Mathematical Induction can be used to prove ...
148 views

### Data structure choice for a query-update-delete problem

Given is an initial set of n keys. Each key k is of the form (p, q). Note that both p and q are positive. At any given point, there are two possible actions: 1) Query-Delete: Given a value s as ...
109 views

### Distinct Binary Heaps

I have $n$ elements out of $n-1$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it. My analysis : I started ...
182 views

### d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$. Then for a ...
143 views

### Solutions to Diophantine Equations using a Min Heap

I've recently come across this problem: Find all solutions to the equation $a + 2b^2 = 3c^3 + 4d^4$ for which $a, b, c, d$ are all less than $100,000$. Hint: use one min-heap and one max-heap. I ...
143 views

### LazyHeap data structure with $O(n)$ Insert, Delete, and Return operations

Consider a data structure called LazyHeap that supports the following operations: INSERT(x): Given an element $x$, insert it into the data structure. It has no cost. DELETE(x): Delete $x$ from the ...
662 views