All Questions
17 questions
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 ...
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
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
0
votes
4
answers
348
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
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
2
answers
70
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 ...
- 145
0
votes
1
answer
3k
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:
...
- 153
1
vote
2
answers
298
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 ...
6
votes
1
answer
2k
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....
- 63
2
votes
2
answers
1k
views
Finding the k-th smallest ternary sum of elements from three different arrays
The problem goes like this:
Given arrays $\{ a_i: 0\leq i \leq n-1 \},\{ b_i: 0\leq i \leq n-1 \} $ and $\{ c_i: 0\leq i \leq n-1 \}$, we want to know what is the $k$-th smallest combination $a_r+...
- 123
2
votes
1
answer
1k
views
Minimum number of nodes in AVL tree
Let T be an AVL tree of height 3. What is the smallest number of entries it can store? Note that a tree with one node (only the root) has the height of zero and stores one element.
The only method I ...
2
votes
1
answer
3k
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 ...
- 123
1
vote
1
answer
2k
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
- 131
1
vote
1
answer
2k
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$ ...
user69093
2
votes
1
answer
550
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
0
answers
81
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 ...
- 173
0
votes
1
answer
1k
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 ...
