Compare the cost of Insert operation and deleteMin operation between a 16-heap a

Question

Compare the cost of Insert operation and deleteMin operation between a 16-heap and a binary heap. Use the number of comparisons between two elements as the runtime metric. Specifically, state how many times each of the two 16-heap operations (i.e., Insert, deleteMin) is faster or slower compared with the corresponding binary heap operation and explain the reason. Note that 16 is a power of 2 number and, therefore, multiplication and division by 16 can be done using bit shift operations, which are fast, i.e., O(1).

Explanation / Answer

Insert DeleteMin

Binary heap : log n log n

16-heap: 1/4log n 4log n

Insertion into 16-heap is faster than binary heap where as deleteMin is slower 16-heap when compared to binary heap.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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