Which of the following is a valid heap? (Each tree is a complete binary tree given in level order, left to right.)
Which of the following is a valid heap? (Each tree is a complete binary tree given in level order, left to right.)
(A) 16, 14, 10, 4, 7, 9, 3, 2, 8, 1
(root 16; children of 16: 14, 10; children of 14: 4, 7; children of 10: 9, 3; children of 4: 2, 8; child of 7: 1)
(B) 16, 14, 10, 8, 7, 9, 3, 2, 4, 1
(root 16; children of 16: 14, 10; children of 14: 8, 7; children of 10: 9, 3; children of 8: 2, 4; child of 7: 1)
(C) 16, 14, 10, 8, 1, 9, 3, 2, 4, 7
(root 16; children of 16: 14, 10; children of 14: 8, 1; children of 10: 9, 3; children of 8: 2, 4; child of 1: 7)
(D) 16, 14, 3, 4, 1, 9, 10, 8, 2, 7
(root 16; children of 16: 14, 3; children of 14: 4, 1; children of 3: 9, 10; children of 4: 8, 2; child of 1: 7)
Show answerHide answer
Correct answer: (B) B
Explanation
(A) fails the max-heap property (4 has child 8). (B) is a valid max heap because every parent ≥ its children. (C) fails (1 has child 7). (D) fails (3 has children 9 and 10; 4 has child 8; 1 has child 7).