CODEWITHSUNDEEP
algorithmpriority-queuemax-heap
taurus05
taurus05

Reputation: 2546

Efficient HEAPIFY method to reduce number of comparisons

Consider a binary max-heap with n elements. It will have a height of O(log n). When new elements are inserted into the heap, they will be propagated in the heap so that max-heap property is satisfied always.

The new element will be added as the child on the last level. But post insertion, there can be violation of max-heap property. Hence, heapify method will be used. This will have a time complexity of O(log n) i.e height of the heap.

But can we make it even more efficient?
When multiple insert and delete are performed, this procedure makes things slow. Also, it is a strict requirement that the heap should be a max-heap post every insertion.

The objective is to reduce the time complexity of heapify method. This is possible only when the number of comparisons are reduced.

Upvotes: 1

Views: 190

Answers (2)

trincot
trincot

Reputation: 350996

The time complexity of the insert operation in a heap is dependent on the number of comparisons that are made. One can imagine to use some overhead to implement a smart binary search along the leaf-to-root path.

However, the time complexity is not only determined by the number of comparisons. Time complexity is determined by any work that must be performed, and in this case the number of writes is also O(logš¯‘›) and that number of writes cannot be reduced.

The number of nodes whose value need to change by the insert operation is O(logš¯‘›). A reduction of the number of comparisons is not enough to reduce the complexity.

Upvotes: 2

greybeard
greybeard

Reputation: 2516

The objective is to reduce the time complexity of the heapify method.

That is a pity, because that is impossible, in contrast to

Reduce the time complexity of multiple inserts and deletes:

Imagine not inserting into the n item heap immediately,
building an auxiliary one (or even a list).
On delete (extract?), place one item from the auxiliary (now at size k) "in the spot emptied" and do a sift-down or up as required if k << n.
If the auxiliary data structure is not significantly smaller than the main one, merge them.

Such ponderings lead to advanced heaps like Fibonacci, pairing, Brodalā€¦

Upvotes: 3

Related Questions