We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [heaps]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
56 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
233 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
368 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
588 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
445 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
680 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
552 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
195 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
60 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
432 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
271 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
108 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
412 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
142 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
495 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
971 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
103 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
825 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
640 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
190 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
688 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
532 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
997 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
295 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
3answers
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
195 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
345 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
473 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
648 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
163 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
426 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
67 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
134 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
854 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
597 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 ...
7
votes
2answers
8k 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 ...
2
votes
1answer
200 views

How to get this upper bound on worst-case heaps?

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the ...
2
votes
1answer
320 views

Can a heap have no elements?

Is it correct to call something with no elements a binary heap? I think it is correct, for one element too, but I'm not sure. It seems to satisfy the definition (from Wikipedia): Shape property: a ...
0
votes
0answers
220 views

What is the time complexity of min-heap based solution to calendar rendering problem

Question: You are given a set of events in a day. Each event has a start and end time. Find the maximum number of concurrent events Solution: First convert events into an array of "Event ...
3
votes
1answer
137 views

Why do you need to fill the first element of array when implementing heap?

I'm looking at Heap data structure implementation from different sources. What I found is that sometimes it's implemented with the first element of array set to magic (default, unused?) value. For ...
3
votes
1answer
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 ...
-1
votes
1answer
328 views

What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
3
votes
3answers
1k views

Ideal value of d in a d-ary heap for Dijkstra's algorithm

I stumbled upon the following statement: By using a $ d $-ary heap with $ d = m/n $, the total times for these two types of operations may be balanced against each other, leading to a total time ...