There is a MAX-heap where each node has four subtrees which are less than it and

Question

There is a MAX-heap where each node has four subtrees which are less than it and this MAX-heap starts out with n values in it. If delete() is called n times to remove the items from heap one by one in descending order, what will be the total cost to delete all elements from heap in this manner?
Note: delete() is the algorithm where we take the value currently in node that needs to be removed and copy it in the root and fix the heap as needed due to data movement.
Be sure to include constants in front of largest order term for this problems. You are looking at the number of data comparisons in worst case if heap starts with n values. There is a MAX-heap where each node has four subtrees which are less than it and this MAX-heap starts out with n values in it. If delete() is called n times to remove the items from heap one by one in descending order, what will be the total cost to delete all elements from heap in this manner?
Note: delete() is the algorithm where we take the value currently in node that needs to be removed and copy it in the root and fix the heap as needed due to data movement.
Be sure to include constants in front of largest order term for this problems. You are looking at the number of data comparisons in worst case if heap starts with n values. If delete() is called n times to remove the items from heap one by one in descending order, what will be the total cost to delete all elements from heap in this manner?
Note: delete() is the algorithm where we take the value currently in node that needs to be removed and copy it in the root and fix the heap as needed due to data movement.
Be sure to include constants in front of largest order term for this problems. You are looking at the number of data comparisons in worst case if heap starts with n values.

Explanation / Answer

There is a MAX-heap where each node has four subtrees which are less than it and this MAX-heap starts out with n values in it.

=> Answer : O(n log4 n)

Explanation : Since Each node has four subtrees, Means each node will spawn 4 branches out of it. If we try to calculate height of the tree. Height of the tree will be log4 n .
We know that delete() will take time equal to height of the tree which is log4 n .
If we perform n delete then total time taken will be nlog4 n . Hence the time taken will be  O(n log4 n)


Thanks, let me know if there is any doubt/concern.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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