HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is the assumption in the max heapify procedure crucial to its implementation?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whythecrucialprocedureitsmaxheapifyimplementationassumption

Problem

While watching MIT's 6.006 Lecture # 4 which is on heaps and heapsort, the professor was explaining why the time complexity of the max_heapify procedure is $O(\lg n)$. It's quite intuitive that it's bounded by $\log n$. But there's a lurking reason also, that affects the implementation, and that reason was the key assumption which has imposed to the procedure, namely the trees rooted at left(i) and right(i) are max heaps. Why is that? Why the assumption plays a role in its implementation? Is it even necessary?

Solution

Heaps support several operations. Among them is the operation of extracting the maximal element. Heaps are constructed so that all supported operations have low complexity. In particular, in order for us to maintain the property that the maximal element is at the root after extracting the maximum, we need the left and right subtrees to be max-heaps as well.

There are other data structures which handle this differently, such as self-balancing binary trees, but these tend to be more complicated, and as a result slower in practice (even though they have the same asymptotic complexity).

Context

StackExchange Computer Science Q#77194, answer score: 2

Revisions (0)

No revisions yet.