Questions tagged [heaps]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
21 views

Why are nodes added from left to right in last level in a Heap?

I understand that in Heaps we add them from left to right. I understand how to add and delete. But why is it from left to right, is there something that prevents it from being right to left or ...
user avatar
-1 votes
1 answer
44 views

Fixing the min-heap after subtracting a value from a couple random elements in it

Given a Min-Heap with $n$ elements. Assume that we choose $\lceil \log_2n \rceil$ elements from the heap (not in any specific order/index's), and we subtract a value $k>0$ from all of their keys. ...
user avatar
  • 164
2 votes
3 answers
134 views

Find the smallest difference between two numbers in a DS in O(1) time

I got an assignment to create a new data structure, with the following rules: Init - O(1). Insert x - O(log$_2$n). Delete x - O(log$_2$n). Search for x- O(log$_2$n). Find max difference between two ...
user avatar
0 votes
2 answers
65 views

Find the largest MinHeap subtree in a given Tree

We are given a rooted tree $T$ of distinct Natural numbers. The goal is to find the largest subtree of $T$ that has MinHeap property. In fact, we want to calculate the largest subset $S$ of nodes, in ...
user avatar
  • 21
0 votes
0 answers
14 views

New Heap after consecutive calls to Realloc and Free

I'm currently spending my time preparing for my exam in Computer Systems. Everything is going smoothly enough, but there is one task I am having problem with understanding. I've been trying to find ...
user avatar
-2 votes
1 answer
71 views

Dividing a binomial heap to 3 equal-sized binomial heaps

Given a binomial heap of $n$ nodes (where $n$ divides by 3), how can I split the heap to three binomial heaps with an equal number of nodes (every heap contains $n/3$ nodes). The time complexity needs ...
user avatar
  • 1
0 votes
0 answers
51 views

binary heap vs regular list for dijkstra algorithm

I'm trying to understand at which densities (for example bounding $|E|^{1.5}<|V|<|E|^2$) is a normal list better than a binary heap (or a fibonacci heap). From what I understand, the runtime of ...
user avatar
0 votes
0 answers
32 views

Transform binary tree to max heap with minimal number of key changes

I am stuck on this interview practice problem and could use some advice. Given a binary tree, assume that you are only allowed to change the values of the keys of the nodes so that the Max Heap ...
user avatar
1 vote
1 answer
67 views

When is a max heap tree invariant under a root removal, followed by a re-insertion of the root?

Let $T$ be a max heap tree with no duplicate values amongst the nodes. When does $T$ satisfy the following. Remove the root, and restructure the tree to satisfy the heap property. Reinsert the root, ...
user avatar
2 votes
1 answer
94 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, ...
user avatar
1 vote
2 answers
37 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 ...
user avatar
  • 13
2 votes
1 answer
44 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 $...
user avatar
0 votes
0 answers
27 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 ...
user avatar
0 votes
0 answers
177 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? ...
user avatar
2 votes
2 answers
77 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 ...
user avatar
0 votes
3 answers
86 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 ...
user avatar
  • 1
3 votes
1 answer
63 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$ ...
user avatar
  • 131
0 votes
0 answers
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 ...
user avatar
  • 167
1 vote
0 answers
59 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 ...
user avatar
0 votes
0 answers
48 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 ...
user avatar
0 votes
2 answers
94 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 ?
user avatar
0 votes
2 answers
96 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.
user avatar
  • 377
0 votes
1 answer
179 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 ...
user avatar
1 vote
1 answer
55 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 ...
user avatar
1 vote
0 answers
57 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$. ...
user avatar
0 votes
1 answer
430 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 ...
user avatar
0 votes
1 answer
137 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 ...
user avatar
  • 101
1 vote
1 answer
149 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 ...
user avatar
  • 49
0 votes
1 answer
96 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 ...
user avatar
  • 49
0 votes
0 answers
54 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 ...
user avatar
0 votes
1 answer
217 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 ...
user avatar
  • 229
1 vote
0 answers
56 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 ...
user avatar
0 votes
0 answers
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: ...
user avatar
0 votes
1 answer
42 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?
user avatar
0 votes
1 answer
544 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&...
user avatar
1 vote
1 answer
547 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 ...
user avatar
  • 13
1 vote
1 answer
93 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 ...
user avatar
  • 151
-1 votes
2 answers
107 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?
user avatar
  • 17
0 votes
2 answers
48 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 ...
user avatar
0 votes
1 answer
207 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. ...
user avatar
  • 1
0 votes
0 answers
138 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 ...
user avatar
0 votes
1 answer
210 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 ...
user avatar
  • 3
0 votes
0 answers
167 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)...
user avatar
3 votes
1 answer
399 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 ...
user avatar
  • 143
2 votes
1 answer
72 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: <...
user avatar
1 vote
2 answers
12k 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 ...
user avatar
0 votes
1 answer
434 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 ...
user avatar
0 votes
1 answer
46 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 ...
user avatar
  • 145
3 votes
1 answer
38 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....
user avatar
0 votes
1 answer
101 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 ...
user avatar
  • 1,145

1
2 3 4 5