Questions tagged [heaps]
The heaps tag has no usage guidance.
247 questions
3
votes
1
answer
1k
views
How to allocate memory in NASM without C functions (x64)?
So I'm using NASM on linux and I was curious how this is done. All the info I can find online uses functions from C like malloc(). Can this be done purely with assembly code? Perhaps via a system call?...
- 31
1
vote
0
answers
83
views
Reorder a Binary Heap to have the smallest elements in one half in linear time
Is there a known algorithm that can reorder a binary heap of size $N$ so that after the reordering
we still have a valid binary heap
the first half of the input ($\frac{N}{2}$ elements) are all ...
- 11
-1
votes
1
answer
57
views
What is the the maximum and minimum amount of nodes in a heap
The title of my question says all that is needed. Some may argue that this is a duplicate question, because some years ago, this same question was made, but I couldn't understand the explanation, then ...
1
vote
1
answer
24
views
How would setjmp differ in runtime environments with stack-allocated vs. heap-allocated stack frames?
I am stumped on Engineering a Compiler, 3rd ed. Section 6.3, Review Question 1. The book uses the term 'activation record' to refer to a generalized procedure frame. The question asks:
In C, '...
- 31
0
votes
1
answer
50
views
Splitting a binomial heap into 3n/8 and 5n/8 binomial heap whereas 8 divides n with O(log(n)) time
I ran into this exercise that says:
With a given binomial heap with n elements and n is divisible by 8, split the heap into 2 binomial heaps, one with 3n/8 elements and the other with 5n/8 elements.
...
1
vote
0
answers
82
views
Update priority of existing item in a minmax heap
Say you have a double ended priority queue in the form of a minmax heap as described here.
What is the most efficient algorithm to update the priority of an existing item?
Assume that
I explicitly ...
- 133
1
vote
1
answer
2k
views
Time complexity to remove an item from the heap
Given an array of size $n$ that has the item of the heap. To remove an arbitrary element from the heap we would need $O(n)$ to find the element and then $O(logn)$ to reheapify if I am commrect, which ...
- 515
2
votes
1
answer
534
views
Prove that the number of comparisons between elements in binary heap build is at most (2n-2)
Question
Prove that the number of comparisons between elements in binary heap build is at most $2n-2$.
$n$ is the total number of the nodes.
Pseudocode
...
- 143
1
vote
1
answer
146
views
Computing the index of the n^{th} ancestor of a node in a perfect binary tree / heap
I think you can compute the index of the n^{th} ancestor of the node at index i using the formula: $\lfloor i / 2^n \rfloor$ where $n \in \mathbf{Z}^+$. Note that I am assuming that the parent node is ...
0
votes
1
answer
135
views
Two Questions About Fibonacci Heaps
I am learning about Fibonacci heaps from the following set of notes: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm. There are 2 things that are confusing me.
Firstly, in the ...
- 101
0
votes
2
answers
125
views
What is the maximum inverse pairs will I have when I build a heap?
Suppose that I have 7 different integers stored in an array. Among those arrange-
ments that can be viewed as a min heap, what is the maximum number of inverse pairs within the array?
1
vote
3
answers
555
views
Why is the heap data structure called 'heap'?
The term "heap" has majorly two meanings in computer science -
The "heap" memory in the context of memory management.
The "heap" data structure as the representation of ...
- 143
1
vote
2
answers
113
views
Partially sorted Max Heap
I need to convert a Max Heap to a "Partially Sorted Max Heap" such that all keys at depth i are smaller than all keys at depth i-1.
What is the most efficient way of doing this? Can this be ...
- 371
-2
votes
1
answer
128
views
Is there an algorithm that can get the minimal element of a min-heap in O(log* n)?
I came across this question when studying for an exam:
given a min-heap that has no prime numbers in it, is there an algorithm that can get and delete the minimum of that heap in O(log* n) ?
The ...
- 1
0
votes
0
answers
45
views
Minimum Heap - Add k to all left keys and heapify efficiently
I've been trying to solve this problem:
Given a minimum heap $H$, which contains $n$ elements, where each of its keys contain natural numbers, as well as $k\in\mathbb{N}$.
Add the value $k$ to each ...
- 113
1
vote
1
answer
355
views
Removing k-smallest elements in a binary min-heap
Assuming a contiguous array implementation of a binary min heap with n elements, is it possible to remove the k-smallest elements in a faster time than $O(k \log n)$...
- 123
0
votes
0
answers
57
views
If you took the permutations of an array and heapified it, will you always get the same heap?
In other words, if I have 10 arrays each with 10 of the same values but scrambled their order and heapified them all, is it possible to have different results?
- 11
0
votes
1
answer
303
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 ...
-1
votes
1
answer
106
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.
...
- 164
2
votes
3
answers
456
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 ...
- 23
0
votes
2
answers
173
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 ...
- 31
-2
votes
1
answer
101
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 ...
- 1
1
vote
1
answer
124
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, ...
- 11
2
votes
1
answer
230
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, ...
- 305
1
vote
2
answers
84
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 ...
- 13
2
votes
1
answer
55
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 $...
- 235
0
votes
1
answer
2k
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
2
answers
196
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 ...
- 173
0
votes
4
answers
347
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 ...
- 3
3
votes
1
answer
74
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$ ...
- 131
1
vote
0
answers
78
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
0
answers
308
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
2
answers
192
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
2
answers
215
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.
- 421
0
votes
1
answer
675
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
1
answer
71
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 ...
- 113
1
vote
0
answers
142
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$.
...
- 243
0
votes
1
answer
3k
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 ...
- 15
1
vote
1
answer
534
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 ...
- 111
1
vote
1
answer
365
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 ...
- 49
0
votes
1
answer
305
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 ...
- 49
0
votes
0
answers
177
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 ...
- 161
0
votes
1
answer
493
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 ...
- 239
1
vote
0
answers
103
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 ...
- 11
0
votes
0
answers
29
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
1
answer
65
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
1
answer
930
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
2
answers
2k
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 ...
- 21
1
vote
1
answer
857
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 ...
- 151
-1
votes
2
answers
488
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?
- 17