Questions tagged [heaps]

The tag has no usage guidance.

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

asymptotic height of d-ary heap

I know that the height of a d-ary heap on $n$ nodes is $\lceil (\log_d (n(d-1) + 1) - 1)\rceil$, but I was wondering how to justify that that's $\Theta(\log_d n)$? I know the definition of $\Theta, O, ...
1
vote
2answers
28 views

How to define formula to determine which group does the element belong to?

I am trying to build a min-max heap tree, here's an example of the tree structure: The tree is a complete binary tree The index in the array of the tree root is 0 and it contains no element. The left ...
1
vote
1answer
34 views

Runtime analysis with multiple parameters: case study with heaps in Huffman coding

While studying a book on algorithms, I came across a question that asked about essentially $d$-ary Huffman coding, where the codeword alphabet has $d$ symbols (the usual case has $d=2$, with symbols $...
0
votes
0answers
19 views

Treap use cases

I am trying to develop an appreciation for the treap data structure; my goal is not to implement one but use boost when the problem calls for this construct. Some use cases, or small problems showing ...
0
votes
0answers
32 views

Is there a difference between Heapify and Bottom-Up/Top-Down heap construction, when using array representation of binary tree?

Won't both the methods ultimately give a max/min heap? So if I am given a binary tree, as an array, and am asked to convert it to a max heap, can I just use the bottom up construction of the heap? ...
2
votes
2answers
67 views

If both could be implemented with the other, what are the differences between priority queues and binary heaps?

I've red that a binary heap can be implemented using a priority queue. I've also red the opposite, that a priority queue can be implemented using a binary heap. This seems strange to me as ...
0
votes
3answers
47 views

How to make a Huffman tree

I'm trying to make a huffman tree based off of some words. I have the frequencies of each character stored using a hashtable, but i need to then make a minheap structure in order to then be able to ...
2
votes
1answer
52 views

What is the analysis that a heap's optimal branching factor is between 2 and 5?

I'm reading the book Advanced Algorithms and Data Structures. It makes the claim that the optimal branching factor $D$ for a heap satisfies $2 \le D \le 5$, and that it is most likely $3$ or $4$ ...
0
votes
0answers
21 views

Why the last elements of the array of heap is itself heap

If we represent a heap using array the 2nd half of the array will be represent the leaf nodes of the heap. But I can not understand for array of length n, all elements in range A[[n/2+1]....n] are ...
1
vote
0answers
46 views

finding max element in a min-max heap structure

I am trying to implement min-max heap structure A min-max heap is a data structure that is identical to a binary heap, but the heap-order property is that for any node, X, at even depth, the element ...
0
votes
0answers
21 views

dijkstra with adjacency list and minimum heap as queue vs adjacency matrix and a normal array as "queue"

Which one should be faster? I have written a script comparing both run time, initially the implementation with adjacency list and minimum heap performs faster, but as the number of nodes/edges ...
0
votes
2answers
89 views

Kth largest element of a Min Heap of size K is always root element

Why the Kth largest element of a Min Heap of size K is always root element of the Min Heap ? How to prove this ?
0
votes
2answers
79 views

Having trouble calculating the asymptotic running time of MAX-HEAPIFY

I don't understand the $T(2n / 3)$ part in the recurrence relation for MAX-HEAPIFY in the book CLRS. There is another post that explains it but I can't realize it.
0
votes
1answer
77 views

When can a (max) heap be a BST?

Cheers, let's suppose we have a MAX heap which does not allow duplicate elements. Is it possible for this heap to be a BST ? Choose the right answer(s) below: A heap can never be a BST A heap is ...
1
vote
1answer
43 views

Given an array A and a minimum heap H which of the following are true?

I got this series of questions, each needs to either be proved or disproved (w/ example). If $A$ is sorted in non-descending order, it is a valid minimum heap. If $H$ is represented by $A$, therefore ...
1
vote
0answers
42 views

Find the median in a full min-heap with at most $\left \lfloor \frac{n}{2} \right \rfloor$ comparisons

I'm thinking to do this recursively using the fact the the left subheap is also a min-heap with its root being the minimum using some variation of Select$\left \lfloor \frac{n}{2} \right \rfloor$. ...
0
votes
1answer
190 views

M + N log N running time for Dijkstra

I'm taking the Design and Algorithms Part -II course in Coursera by professor Tim Roughgarden. In one of the classes, he mentioned that the running time for Dijkstra is $O(m \log n )$ using the heap ...
0
votes
1answer
61 views

Fibonacci Heap: Could i always consolidate?

Right now I am learning about Fibonacci heaps for the first time. After the minimum Node of a Fibonacci heap is extracted you consolidate it, to give it a better structure and execute future ...
1
vote
1answer
96 views

How to do binary search on a path in a binary heap

I am trying to solve this question: Let's say you have a binary heap and an index $i$, design an algorithm that finds if a number $x$ appears in the path between the root of the heap and $heap[i]$ in ...
0
votes
1answer
47 views

How to prove that a binary heap can't be sorted with complexity that better than O(nlogn)

I am trying to prove that you can't sort binary heap with better complexity than O(nlogn). We proved at class that every sort based on comparison can't have better cocmplexity than O(nlogn) and i ...
0
votes
0answers
42 views

Why is the stack smaller than the heap?

From what I understand, stack and heap grow in opposite directions: However, why is it then the case that the stack is sometimes statically allocated, and generally smaller than the heap? We hear ...
0
votes
1answer
74 views

Memory allocation of priority queues

So, i faced this question during a pratice quiz i have no idea why " all of the elements are located contiguously in memory " wrong!! My logic is that priority queues are made of binary ...
1
vote
0answers
49 views

Fibonacci Heap that consolidates after every step

The lecturer of my graduate algorithms course suggested that, even if a Fibonacci Heap would consolidate its tree list after every operation (not just when doing deleteMin()), most operations would ...
0
votes
0answers
21 views

How to find diffrenet ways to implement merge and delete_min operation in binomial heap?

I have searched on the internet to find different ways to learn binomial heap operations. What I have found is not quite helpful for me.For example, for delete min operation the algorithm says: ...
0
votes
0answers
25 views

Characteristics of max-heaps

I have just reached the priority queue section where the book I am currently reading about algorithms talked about max-heaps and min-heaps. As a part of its structure, the book would ask the reader a ...
0
votes
1answer
41 views

Why we can't create a binomial heap in max-heap format?

Why we can't create a binomial heap in max-heap format instead of min-heap format?
0
votes
1answer
381 views

How to derive the worst case time complexity of Heapify algorithm?

I would like to know how to derive the time complexity for the Heapify Algorithm for Heap Data Structure. I am asking this question in the light of the book "Fundamentals of Computer Algorithms&...
1
vote
1answer
375 views

prove that in binary heap buildheap function does at most 2N-2 comparison

prove that in binary heap buildheap function does at most 2N-2 comparison I don't know how should I prove it I need some hint thanks. buildheap procedure: we have n element and we build a heap at ...
1
vote
1answer
80 views

k-th smallest element in sliding segment

Consider an array $a[1\ldots n]$ and another array $l = a[0]$ (initial value). At each turn we may add next element to array $l$, or remove first element from array $l$. F.e. after first iteration it ...
-1
votes
2answers
92 views

Finding a maximum element in min heap

i need to say : Where can be a maximum element in a min heap when all the elements are different?
0
votes
2answers
35 views

Is the heap in "Data Structures Algorithms in Java" by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?

In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an "Example of a heap storing 13 entries with integer keys. The last ...
0
votes
1answer
172 views

How to draw the heap for an array in Java?

I have an assignment to draw the heap after an ArrayList and a LinkedList is created. ...
0
votes
0answers
96 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
99 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 ...
0
votes
0answers
142 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)...
3
votes
1answer
294 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
60 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: <...
1
vote
2answers
8k 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
265 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
45 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
32 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
79 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
1k 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: ...
1
vote
1answer
247 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
53 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
1answer
144 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?
-1
votes
1answer
82 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 &...
1
vote
2answers
63 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
54 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
171 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 ...

1
2 3 4 5