Questions tagged [heaps]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
33 views

Why do we need MinHeap for Meeting Rooms 2 Leetcode problem

I came across this problem online which is a Leetcode premium problem. Most of the people are solving this using Minheap. To me using minHeap for this seems like repetitive way to solve a problem if ...
0
votes
1answer
17 views

Range search in a max-heap

I am having trouble with coming up for a suitable algorithm for this question. A max-heap is essentially visualized as a binary tree not a binary search tree. Also the runtime of the algorithm must ...
-1
votes
0answers
49 views

Better Priority Queue operation time complexity without using heap

My implementation of a priority queue using a circular array (in pseudocode): ...
1
vote
0answers
25 views

Essence of the cost benifit obtained by using “markings” in Fibonacci Heaps (by using a mathematical approach)

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al The authors deal with a notion of marking the nodes of Fibonacci Heaps with the ...
1
vote
0answers
29 views

Intuition behind the entire (amortized) concept of Fibonacci Heap operations

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al The potential function for the Fibonacci Heaps $H$ is defined as follows: $$\Phi(H)...
2
votes
1answer
48 views

What are the disadvantages of Fibonacci Heaps?

A Fibonacci heap is a data structure for priority queue / heap operations. It seems to have the best complexity for all operations: Since it has the best performance, why not use it everywhere? What ...
2
votes
1answer
40 views

Clarifying $\sum_{h=0}^{\lfloor lg(n)\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n)\rfloor}\frac{h}{2^h})$ in BUILD-MAX-HEAP

I was going the text Introduction to Algorithms by Cormen et. al. Where I came across a step in the analysis of the time complexity of the $BUILD-MAX-HEAP$ procedure. The procedure is as follows: <...
0
votes
0answers
15 views

How to pick a random index in an array based on the index's value?

While solving a problem on leetcode, I used a heap to give the largest probable value. The problem statement is as follows: Given an array w of positive integers, where w[i] describes the weight of ...
0
votes
1answer
73 views

What are the minimum and maximum numbers of elements in a heap of height h?

I came across the question: What are the minimum and maximum numbers of elements in a heap of height $h$? To which I came up with this theory: $$\sum_{i=0}^{h-1} 2^i = 2^h-1$$ $2^h-1$ is the ...
0
votes
1answer
16 views

Method to change value in a key for a min heap

How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with ...
0
votes
1answer
30 views

Use tree in-order traversal to determine whether a BST or Heap

Given these in-order traversal lists: 1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19 2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17 I need to determine whether each one of those lists represent a valid BST ...
2
votes
1answer
28 views

Order notation subtractions in Fibonacci Heap

Can order notation on its own imply: $O(D(n)) + O(t(H)) - t(H) = O(D(n))$ My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if the constant is > 0....
0
votes
1answer
36 views

Does the heap property in the definition of binary heaps apply recursively?

The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property, the key ...
0
votes
1answer
101 views

Find height of a ternary tree

Ternary heap is like a binary tree, just every node can have up to $3$ sons and not $2$. I try to bound the number of nodes in the heap, $n$, using the height of the heap $h$. The solutions get to: ...
2
votes
1answer
27 views

What is the difference in time-complexity for sorting these 2-d arrays?

Let $A$ have $n/10$ rows, $10$ columns and $n$ overall elements Let $B$ have 10 rows, $n/10$ columns and $n$ overall elements. It is given that each row is sorted in ascending order, Can you sort ...
1
vote
1answer
48 views

How to solve the following equation: $(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$?

I came with this interesting question and could understand how did we get to this equation: $(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$ But in the next step, it reached to the following ...
0
votes
0answers
31 views

creating a binomial heap with only pointer object references

I have a problem where I must make a binomial heap in Python. I have almost all of the methods working except for the bubbleUp method. The problem I am having is ...
0
votes
0answers
21 views

Is It Of Much Practical Use To Actually Use Fibonacci Heap Over Min Heap In Dijkstra Algorithm?

I know that to get the best technical running time in Dijkstra's shortest path algorithms, using a Fibonacci Heap is the correct way to go. However, the internet and in CLRS state that Fibonacci Heap ...
0
votes
1answer
39 views

Number of nodes of given height in binary heap

Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n$-element binary heap. How can I show this? Or, how can I prove this?
0
votes
1answer
23 views

reordering a max heap that the values of one of her subtrees has been changed

Let $H$ be a max binary heap with $n$ elements (vertexes). Pick a vertex $z$ in the heap with height of $k$ ($0<k<\lg n$) To every element in the sub heap of $z$ we add the constant value $c &...
0
votes
0answers
30 views

Is it necessary that Minimum/Maximum Heap must be a Binary Heap?

I find this extremely wrong, that a lot of books, articles, video tutorials, online courses or trainers define Minimum/Maximum Heap data structure as a particular type of the Binary Heap data ...
2
votes
1answer
35 views

How to solve this summation of ceiling function in BUILD-MAX-HEAP algorithm

I am stuck on solving this problem and cannot understand how is the ceiling function omitted or solved. Please help. The equation: $\sum_{h=0}^{\lfloor\lg n\rfloor} \lceil\frac{n}{2^{h+1}}\rceil O(h)...
1
vote
0answers
27 views

Modify Fibonacci Heap to Have a Linear Chain of Marked/Unmarked Nodes Only

In CLRS book there is an exercise (19.4-2), the aim of which is to create a linear chain of nodes by a sequence of Fibonacci-Heap operations. I have solved the problem by recursively making a union ...
0
votes
2answers
39 views

Is destructuring a heap (taking down a heap) also O(n) like building a heap? If so, can the selection problem be solved by this method in O(n) time?

If we can build up a heap with time O(n), can we take down a heap also by O(n)? (by delete-max repeatedly). Intuitively, it may feel it is, because it is like the reverse of build it up. (Building a ...
0
votes
0answers
25 views

Quick question about max heap

Suppose that we have a max heap and that it contains duplicate values .Is it always true that nodes with same value are adjacent(neighbors)?I think it is true because if there was any other node being ...
1
vote
0answers
30 views

relationship between binary numbers and binomial heaps

I understand that a binomial heap can be represented as binary numbers according to the degree of each tree but what exactly is the relationship between inserting a new node into the binomial heap and ...
0
votes
0answers
36 views

Efficient way to convert d-ary to binary heap

Even though a general-purpose algorithm is desired, I'm specifically interested in the case that d is 4 (convert 4-ary to 2-ary).
1
vote
0answers
76 views

finding the parent index in an interval heap (stored on an array) given a child index

an interval heap is a binary tree stored on an array where the size of each node is 2. i would like to be able to find the index of a parent and find one of the child indices given the index of a ...
0
votes
1answer
66 views

Time complexity of a 2-heap question

The problem statement is pretty straight forward: given an array of integers and a window size, return an array of doubles of the median of each window. arr = 1, 3, 5, 10, 6, 9, 2 k = 3 would yield ...
1
vote
0answers
18 views

How to compute the general term formula for the number of full binary tree heaps that can be formed with distinct elements?

The number of possible heaps that are full binary trees of height $h$ and can be formed with ($n = 2^h - 1$) distinct elements can be computed by recursion: $$ a_h = {2^h - 2 \choose 2^{h - 1} - 1} a_{...
1
vote
1answer
66 views

Max heap and array relation

This question is about max heap and array Suppose there is max heap $h$, with $n$ data items already stored in $h$. An array that is formed by inserting a value larger than all the values in $h$ at ...
0
votes
0answers
24 views

faster heap construction cost equation

can someone try to explain the following formula? I don't understand what does "<=n" and "<=2n" mean in this formula , it is my first time look at summation formula with inequality signature. ...
2
votes
1answer
224 views

Dijkstra without decrease key

I was reading though this paper, which suggests using dijkstra without edge relaxation, but to rather to just insert new nodes, cf page 16 for the pseudo code. But to me the code looks wrong. I think ...
0
votes
1answer
74 views

Heap down - What is math logic and intuition behind $\sum_{i=1}^{\log n}(\log n - i) \times 2^i $

In heap (bubble down) we have the formula : \begin{eqnarray*} \sum_{i=1}^{\log n}(\log n - i)\times 2^i & = & \log n\sum_{i=1}^{\log n}2^i -\log n\sum_{i=1}^{\log n}i\times2^i \\ & = &...
2
votes
1answer
42 views

Clarification about conclusion of $Θ(nlogn)$?

Why the first part of formula is equal to $2 * 2^2 + ... + 2^{log(n)} = 2^2 + 2^3 +...+ 2^{log(n)} = 2^3 +...+ 2^{log(n)} =... +2^{log(n)}$ What is the logic behind ($2^{log n +1} - 2{log n}$) ? I ...
-1
votes
1answer
92 views

Implement heap using stack data structure

I want to implement a heap using the stack data structure. I have searched a lot on the internet. But I do not get any clue how to implement it. Can you please help me to implement a heap using the ...
1
vote
1answer
55 views

Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?

From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my ...
0
votes
1answer
57 views

3-heap max heap

I have this 3 heap max heap that I need to write the array for it, but I'm not sure how. Would it just be 20,18,13,15,11,12,16,10,9,11,13,2,9?
0
votes
2answers
39 views

inserting into min heap

These are the instructions I been given : What does the array look like at each step when inserting "2" into the following min-heap? Give your answer as comma-separated numbers, with a ...
3
votes
1answer
115 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 ...
1
vote
1answer
152 views

How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))

We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki "This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n ...
1
vote
3answers
905 views

Why is heap insert O(logN) instead O(n) when you use an array?

I am studying about the arrays vs heap for make a priority queue For check the heap implementation I am reviewing this code: Heap , but I have the following question. Heap is based on array, and ...
0
votes
1answer
314 views

heap data structure complexity

I'm trying to count running time of build heap in heap sort algorithm ...
4
votes
1answer
365 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....
0
votes
1answer
115 views

Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?

I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access... My question though ...
3
votes
1answer
68 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 ...
1
vote
1answer
33 views

What is the index of the leftest child of node in a k-nery heap?

Suppose the root node‘s index is 1, what is the index of the leftest child of a node e in a k-nery heap? What is the parent‘s index of a node in k-nery heap? All questions regarding my problem I ...
2
votes
2answers
64 views

Number of possible heaps on $\{1,…,2^h-1\}$

Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it. Definition A binary tree is ordered ...
0
votes
0answers
33 views

When inserting an element in a priority queue and the heap size is already at max capacity, should you output an error OR increase the array size?

I'm currently learning about how to implement priority queues using heaps, but I've hit a wall while trying to implement the insertion operation. Assume that the size of the array storing the ...
1
vote
3answers
900 views

Why is Binary Heap never unbalanced?

My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?...

1
2 3 4 5