# Questions tagged [heaps]

The tag has no usage guidance.

176 questions
Filter by
Sorted by
Tagged with
100 views

### Randomized meldable heap - meld is oversimplified?

On both Wikipedia and the paper it was introduced the randomized meldable heap uses the following procedure to meld two heaps: ...
502 views

### How to construct a max heap that preserves insertion order for duplicate elements?

I have a priority queue (using a max heap) that preserves insertion order for duplicate priorities, such that equal priorities fall back to FIFO behaviour. I'm doing this by creating a node with the ...
170 views

### Why is a Fibonacci-Tree of rank 1 consolidated with one of rank n in this Fibonacci-Heap?

In the solution to problem 2 of this exercise sheet: The height of $n$-node Binomial Heap is always $O(\log{n})$. Show that this is not the case for Fibonacci Heaps by exhibiting, for ...
17 views

### Why can't popmin in binomial heap just take the main root value?

Why is there a need to scan each root node of the binomial trees in a binomial heap to find the minimum? For example, why can't the true root of the binomial heap, the one that leads to the root ...
1k views

### Worst case time complexity of heap sort

I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows: ...
48 views

### Number of Minheaps Possible

The number of possible min-heaps containing each value from {1,2,3,4,5,6,7} exactly once is: My approach went like this: fixing 1 in the root for the remaining 6 elements we can choose 3 of them and ...
43 views

### Is there an efficient way to insert n items into an n^2 sized heap

I am aware of a O(n) algorithm for constructing a new heap of n items, this is better than repeatedly inserting into an empty heap which takes O(nlogn). I would like to know if there is something ...
1k views

### Find K largest elements using a priority queue [duplicate]

Say we have a Priority Queue of size 1000 that is implemented using Max Heap. Now if i want to get the top 5 elements, the most laid back method is to poll the maximum 5 times, resulting in a set of ...
61 views

### Implementing SUM(i,j) and CHANGE(i,j) in O(log(n)) using a datastructure with O(n) space complexity

I have two operations: $Sum(i,j)$ : Calculate $A[i]+A[i+1]+....+A[j]$ $Change(i,x)$: Set $A[i]=x$ I need to implement these operations in an appropriate data structure using $O(n)$ space ($n$ is ...
249 views

### Is it possible to find the nodes larger than k in a min-max heap in O(m) time?

Is it possible to find the nodes larger than $k$ in a min-max heap in $O(m)$ time, where $m$ is the number of nodes larger than $k$? If it is possible, then how do I implement the rest of the ...
380 views

### implementing ExtractMin on a Max-heap in O(log(n)) time

Is it possible to implement extractMin on a Max-Heap in O(log(n)) time, and if so how? Or do you need a more elaborate structure like a max-min heap?
609 views

### How to find kth largest element in (max) priority queue in O(m) time?

Here is my exercise. FINDLARGEST(k): return the elements in the heap with key >=k" ... "expand the priority queue (max-heap) so that it supports FINDLARGEST(k) in O(m) time, where m is the number ...
477 views

### The time complexity for finding the kth smallest number in a min-heap [duplicate]

Suppose that $k < \sqrt n$, what is the time complexity to find the $k_{th}$ smallest number in a min-heap? I thought that we can remove the root element for k times and each time we apply heapify?...
1k views

### To find median of k sorted arrays of n elements each in less than O(n*k*log(k))

How to find median of k sorted arrays each of length n? Note that total elements would be n*k. I know it can be done in O(n*k*log(k)) using merge technique. I am looking for a better time efficient ...
1k views

### Building heaps and heapsort using linked list

I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list. One of the answers ...
742 views

### The maximum number of nodes in a heap tree of degree d and depth k

The maximum number of nodes in a binary tree of depth k is defined by 2^(k+1)-1, but the same rule doesn't appear to work for heap trees of different degrees. Let's say I have the following tree of ...
578 views

### Why can't we sort an Array in O(n) using Fibonacci Heap?

If we can insert to a Fibonacci Heap in O(1), and increase-key and find-min in the same W.C time complexity, then why can't we sort an array in time complexity O(n)? Given an array with n elements: ...
203 views

### Is there an example of an AVL tree that is taller than a binary heap?

I am curious because I took a quiz and answered false to the question: "The height of an AVL tree may be greater than the height of a binary heap with the same elements." I have been trying to think ...
2k views

### How huffman tree uses MinHeap?

As far as I know, a minheap is data structure whose parent node's value is less than child node and maxheap is when parent node is greater than child node. Here they have used minheap. But as the node ...
63 views

### Proving that a specific Fibonacci heap can't exist [duplicate]

I was asked to describe how I would build a Fibonacci heap that consists of 1 tree with 7 vertices, 2 of them are leaves, and 2 of them are fathers that have a leaf as their son. From what I see, ...
2k views

### Merge 2 Binary Heaps

I want to merge $2$ binary heaps. Which is the fastest algorithm to do so. Also would like to know its time complexity. I know how to do it linear time $O(n)$, I want to know if there is something ...
477 views

### Fibonacci Heap / Binomial Heap - Decrease Key

I've been implementing a Fibonacci Heap in C this past week and today I just hit a mental roadblock that I can't figure out. Decrease Key is a function that almost all min heaps have (vice versa with ...
281 views

### Using Pascal's Triangle to implement queues and stacks using heaps

I have the following question as homework in an algorithms, analysis and data structures class: And here's an answer I wrote up: A queue is a first-in-first-out data structure. A heap is a data ...
110 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 ...
431 views

### Given a binary min-heap, getting a sorted array of the $\log n$ smallest elements

Let's say we have a binary min-heap of size $n$, and we want to get an array of the smallest $\log n$ values in the heap, sorted. What is the best complexity that we can get and how do we implement it?...
143 views

### Build max heap in which all the nodes at certain level are less than all the nodes at the level before them

Max-heap is called a "strong" max-heap if all the nodes at certain level are less than all the nodes at the level before them. What is the most efficient way to build such a heap from a given array? ...
1k views

### Algorithm to find k elements following the median in sorted order

I have the following problem: Given an unsorted array A of size n, print the first k elements in A larger than its median. Here's my approach to the problem: ...
84 views

### Treaps are expected weight-balanced?

In a previous question there was a definition of weight-balanced and a question regarding red-black trees. This question is to ask the similar question, but for treaps. The question is: Is there ...
523 views

### Complexity for checking if an array is a min-d-heap

The problem is this: Let us have an int array of length n. Find an algorithm to determine if the array represents a min-d-heap. My solution: We start from the first index in the array, and compare ...
1k views

### Rotations in a treap

I have a treap like the first image and I want to reach the second image to restore min heap order property. I can't understand which kinds of rotations have been done. Image 1 Image 2
112 views

### Probability of finding the maximum element in a heap

You are given a minimum heap, with probability going to left is 50% and going to right is 50%. What is the probability that You will land up on a maximum element in the heap? For this scenario since ...
841 views

### The number of nodes in a binary tree

If a binary tree is both a max-heap and an AVL tree, what is its largest possible number of nodes, assuming all keys are different?