A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have...

Transcribed Image Text:

A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children. Consider a d-ary heap that's implemented in an integer array a[], and starts from index 0, i.e., a[0] is the root of the tree. The d-ary heap has the max heap property, where a node is at least as large as any of its children. (a) Consider a node in the heap at index k that has a parent and d children. What are the indices of its parent, and children? (b) What is the height of the heap if it had n elements? A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children. Consider a d-ary heap that's implemented in an integer array a[], and starts from index 0, i.e., a[0] is the root of the tree. The d-ary heap has the max heap property, where a node is at least as large as any of its children. (a) Consider a node in the heap at index k that has a parent and d children. What are the indices of its parent, and children? (b) What is the height of the heap if it had n elements?