Count the heap orderings of the labels $1,\dots,7$ on a complete binary tree with 7 nodes (root, 2 children, 4 leaves). A min-heap needs every parent smaller than its children.
The smallest label, 1, must be at the root.
The remaining 6 labels are split between the left and right subtrees (3 nodes each): choose which 3 go to the left: $\binom63=20$ ways.
Each 3-node subtree (a root with two leaf children) has the smallest of its 3 labels at its root, and the other two can be placed in the 2 leaves in 2 ways.
Number of heaps $=\binom63\times2\times2=20\times4=\mathbf{80}$.
More Binary Heaps questions
GATE 2015 CS (CS1) Q37– Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Array…
GATE 2016 CS (CS1) Q47– An operator `delete(i)` for a binary heap data structure is to be designed to delete the…
GATE 2014 CS (CS2) Q22– A max-heap priority queue initially has level order 10,8,5,3,2. Insert 1 then 7. Find the…
GATE 2016 CS (CS2) Q44– A complete binary min-heap contains each integer 1 through 1023 once. Root depth is zero.…
GATE 2011 CS Q33– A max-heap has parent values at least their children’s values. Which displayed tree is a…
GATE 2015 CS (CS2) Q22– A complete binary tree has max-heaps as the left and right subtrees of its root. Which…