CODEWITHSUNDEEP
c++treeheapbinary-treepriority-queue
Agent 0
Agent 0

Reputation: 401

Maintaining Heap Property

Which is better (1 or 2)?

Reference: http://www.cs.sfu.ca/CourseCentral/225/johnwill/cmpt225_09heaps.pdf (Heap Insertion - slide 16) written by Dr. John Edgar.

It would be great if you guys can clarify why one of the methods above is better?

Upvotes: 0

Views: 672

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 133975

With a binary heap implemented as an array, there are in general two ways to implement insertion: top-down or bottom-up. Slide 17 of the linked PDF describes the bottom-up way of doing things. It adds the new item at the end of the heap (bottom-most, left-most position), and bubbles it up. That is an implementation of strategy 1 shown on Slide 16.

From a performance standpoint, this is the better method simply because, on average, it requires fewer iterations to fix the ordering. See Argument for O(1) average-case complexity of heap insertion for a detailed explanation of why that is.

The top-down approach, which corresponds to strategy 2 on Slide 16, requires that every insertion make O(log n) comparisons. This strategy starts at the root and sifts the item down through the heap. If the new item is smaller (in a min-heap) than the node it's being compared against, it replaces the item at that node, and the just-replaced item has to be pushed down. This continues until you reach the bottom of the heap. There is no "early out" possible because you have to end up putting a new item in the heap at the leaf level.

I never really thought of it as making sure of the ordering first, and then ensuring completeness, but that's essentially what the top-down method is doing.

The second strategy requires more iterations per insertion, and also does more work during each iteration to maintain the ordering.

Upvotes: 1

Related Questions