Consider a quad max-heap. A quad max-heap is like a binary max-heap, but nstead

Question

Consider a quad max-heap. A quad max-heap is like a binary max-heap, but nstead of 2 children, nodes have 4 children. (a) How would you represent a quad max-heap in a array? (b) What is the height of a quad max-heap of n elements in terms of n and 4? (c) Give an efficient implementation of HEAP-EXTRACT-MAX. Analyze its running time in terms of 4 and n of 4 and n time in terms of 4 and n (d) Give an efficient implementation of MAX-HEAP-INSERT. Analyze its running time in terms (e) Give an efficient implementation of HEAP-INCREASE-KEY (A,i, k). Analyze its running

Explanation / Answer

(a) The quad-heap can be represented in the same way as a binary heap.

The element at index 1 in the array will contain the root, followed by its four children and so on.

The element at index i will have its children at indices 4i-2, 4i-1, 4i, 4i+1.

So, element at index 2 will have its children at 6,7,8,9.

(b) As the height of a binary heap is log2n, similarly the height of a quad heap will be log4n.

(c) The implementation of extract-max in quad heap is same as that in a binary heap which is as follows:-

1. Display the element at the root.

2. Replace the root of the heap with the last element on the last level.

3. Compare the new root with its children, if they are in the correct order, stop.(If the node is at index i, then its children are at the indices 4i-2, 4i-1, 4i and 4i+1.

4. If not, swap the element with one of its children and return to the step 3.

The time complexity is proportional to the height of heap, i.e, O(log4n).

(d) The implementation of insert is also very simple in quad heap. It is as follows:-

1. Add the element to the bottom level of the heap.

2. Compare the added element with its parent, if they are in the correct order, stop.(If the node is at index i, then the parent is at the index floor(i/4 + 0.5).

3. If not, swap the element with its parent and return to the step 2.

The time complexity is proportional to the height of heap, i.e, O(log4n).

(e) This function is performed as follows:-

1. Increase the value of element at index i to k.

2. Compare the added element with its parent, if they are in the correct order, stop.(If the node is at index i, then the parent is at the index floor(i/4 + 0.5).

3. If not, swap the element with its parent and return to the step 2.

The time complexity of this operation is also O(log4n).

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.