Discussion
Which one of the following sequences when stored in an array at locations \(A[1], \ldots, A[10]\) forms a max-heap?
Answer: B
The max-heap is 23, 17, 14, 7, 13, 10, 1, 5, 6, 12.
In an array heap the children of \(A[i]\) are \(A[2i]\) and \(A[2i+1]\), and every parent must be at least as large as its children. For this sequence:
- A[1] = 23: children 17 and 14
- A[2] = 17: children 7 and 13
- A[3] = 14: children 10 and 1
- A[4] = 7: children 5 and 6
- A[5] = 13: child 12
Every check passes. The others each break the rule once: in the first sequence A[3] = 10 has the child A[6] = 14; in the third A[5] = 13 has the child A[10] = 15; and in the fourth A[4] = 1 has the children 12 and 7.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development