Questions tagged [heaps]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
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: ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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: ...
0
votes
0answers
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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?
1
vote
1answer
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 ...
1
vote
2answers
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?...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
5
votes
2answers
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: ...
0
votes
1answer
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 ...
0
votes
3answers
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 ...
0
votes
0answers
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, ...
-2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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?...
2
votes
1answer
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? ...
1
vote
3answers
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: ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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
1
vote
0answers
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 ...
-1
votes
1answer
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?
3
votes
0answers
663 views

How to determine the fewest number of comparisons for Heapsort?

I'm currently doing an exercise that asks to prove that Standard-Heapsort requires at fewest $\frac{1}{8} n \log(n) - O(n)$ comparisons, in its best case. In its average case, Heapsort only requires $...
1
vote
2answers
200 views

Worst Case Scenario in MaxHeapify

First - I've seen and thoroughly read all the similar questions. None of them solves my problem. I've read them all, and seen lectures and asked my Prof but no one was able to answer. They all at most ...
0
votes
1answer
706 views

Why is Heapsort in O(n log n) if not all n operations take time log n?

let's consider that we already have constructed heap array. so from this, when we do heap sort, the number of elements that have to be sorted decreased. I mean heap decrease.(which also means heap ...
0
votes
1answer
597 views

Time complexity of BFS with min heap

Given a matrix of size m x n, I am trying to traverse it using BFS from top left corner to bottom right corner. Instead of using a normal queue for BFS, I am using a min heap. For each cell, I am ...
1
vote
1answer
1k views

Best way to merge 2 max heaps into a min heap

Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this? The easiest way is to consider 2 max heaps an array with $2n$ ...
1
vote
1answer
312 views

Is this a legal Fibonacci heap?

Imagine a Fibonacci heap with 1 tree: a root node, 4 child nodes (to that root node), with 2 of them being leaves and the other 2 having 1 child each (7 nodes total). Is this a legal Fibonacci heap? ...
4
votes
4answers
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 ...
2
votes
1answer
201 views

The Height of subtree in Heap

In order to find the recurrence function of The Height in Heap, the following figure is drawn. Question 1: How can we compute the height if Right subtree in form of Log in base 3, and why do we have ...
0
votes
0answers
2k views

Bubble down implementation for min-heap

While going through bubble_down implementation for min-heap in The Algorithm Design Manual By Steven Skiena, since routine ...
1
vote
1answer
349 views

Number of nodes of height $h$ in a heap or almost complete binary tree

I came up with the following statement: If there are $X$ nodes of height $h$ in an almost complete binary tree, there can be at most 1 node of height $h$ that is not full. That is to say, $X-1$ ...
0
votes
0answers
484 views

How to build a heap better than Incremental and In-place method using decision tree?

For an array A = [a1, a2, a3, a4] of distinct numbers, I have built heap using binary decision tree by Incremental and In-place method. Incremental method: In-place method: Is there a way to build ...
0
votes
2answers
713 views

Heap sort best case time - $\mathcal O(n)$?

It is given $\mathcal O(n\log n)$ everywhere but in best case it should be $\mathcal O(n)$, isnt it ? The argument here is, If my input has all the same keys, then every time I delete the root, I do ...
4
votes
2answers
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 ...
1
vote
2answers
459 views

What is the time complexity for getting the size of a heap?

Assuming the regular Heap ADT. What is the time complexity of getting its size ? I tend to think that because insert is O(log(n)), then I always know the last index of my heap. So in order to get ...
0
votes
0answers
69 views

Analysis on comparisons in a heap-like sorting algorithm

I've stumbled a heap-like sorting algorithm on the Internet as followed: $\\$ For convenience, given a list of $2^n \; (n \in \mathbb{N^*})$ distinct numbers to be sorted increasingly. Step 1: From ...
0
votes
1answer
135 views

How to compare an experimental study with amortized times

I have an implementation of a data structure I have to study for a group project (Fibonacci heaps if you're interested). I'm asked to compare the theoretical results of the operations in amortized ...
0
votes
1answer
872 views

Merging two complete heaps

Suppose you have two heaps each containing $2^k - 1$ elements. Design an efficient algorithm for merging these two heaps into a single heap. My approach was to assume two heaps are maxheap. Create ...
4
votes
4answers
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 ...