The GATE Grind

GATE 2018 CS – Question 56

Programming and Data Structures · Binary Heaps · 2 marks · Numerical answer

The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is ________.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 80

Explanation

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.

Number of heaps $=\binom63\times2\times2=20\times4=\mathbf{80}$.

More Binary Heaps questions

All Binary Heaps questions →