reopened by
3,198 views
2 votes
2 votes
The number of ways in which the numbers 1, 2, 3, 4, 5 can be inserted into binary heap. Such that resulted binary heap is max heap ________.
reopened by

3 Answers

3 votes
3 votes

The answer is 8.

5 4 3 2 1

5 4 3 1 2

5 3 4 1 2

5 3 4 2 1

5 4 2 1 3

5 4 2 3 1

5 4 1 2 3

5 4 1 3 2

So total 8 ways.

so the number of binary heaps with N distinct elements will be
f(N) = C (N−1, L) * f(L) * f(R)

See this: http://qa.geeksforgeeks.org/1970/qa.geeksforgeeks.org/1970/how-many-min-max-heaps-can-be-constructed-with-numbers-1-to-n

Other Approach: https://gateoverflow.in/197327/datastructres

edited by
0 votes
0 votes
4 ways

As we can choose one of the arrangement from 4,3 or 3,4

and 1,2 or 2,1

and 2,1 choose as a left subtree of the tree
0 votes
0 votes
Try to think in this way....

we have to make max heap, so root element will be greatest among them and that is 5.

4 is one of child of 5(fixed), it can be left child or right child.

if 4 is left child of root node of 5 then we left with 3 elements and can arrange in 3! ways= 6 ways

and if 4 is right child, then left child will be 3 only of root node of 5. And then only 2 ways that we can arrange node 1 & 2.

so total 6+2= 8 ways.

Related questions

434
views
1 answers
2 votes
Thor-o-s asked Sep 1, 2022
434 views
Can anyone please explain how to find “ i “ smallest elements from an array whose elements are distinctPlease use max heap to explain the working input : n distinct e...
755
views
1 answers
0 votes
atulcse asked Jan 16, 2022
755 views
Consider the following graph:Find the total number of max-heap possible orderings with elements 12, 10, 1, 5, 7, 9, 8 such that each element is filled in one node of the ...
2.8k
views
1 answers
1 votes
sripo asked Nov 15, 2018
2,812 views
This question is in CLRS,if we have a max heap it is always in sorted order(descending) order.And by extension if we have min heap the array is sorted in ascending order....
1.1k
views
0 answers
1 votes
Balaji Jegan asked Jun 4, 2018
1,120 views
How many max-heaps can be formed with the following elements?$\{1,1,1,2,2,2,3,3,3,4,4,4\}$