0

  • Brief Background: I am studying the steps for maintaining a heap property when insertion occurs. Here is an interesting problem:

  • Question: There are two general strategies that could be used to maintain the heap properties:

    1. Make sure that the tree is complete and then fix the ordering or
    2. Make sure the ordering is correct first and then check for completeness.

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?

Agent 0
  • 361
  • 1
  • 5
  • 17

1 Answers1

1

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.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • Ok, that makes sense. It all has to do with the number of iterations the program takes to main the ordering. Therefore, it is best to check completeness and then fix the ordering. Thanks for your clarification, it now makes sense to me :) – Agent 0 Dec 06 '17 at 05:07
  • 1
    @Kourosh: And you don't even have to "check completeness" in the first case. Placing the new item in the proper place ensures completeness by definition. – Jim Mischel Dec 06 '17 at 05:09
  • yes you are right, we don't check for completeness. Insertion occurs at the size of the array, and then bubble up (i.e, reheap up) algorithm is called to place the item in the right position, thus fixing the order. Also, now I remember why my professor recommends to use bubble up after insertion and bubble down after deletion (i.e, less work). – Agent 0 Dec 06 '17 at 05:30
  • The wording of the slide 16 was confusing at first, but thinking about it logically, it is reasonable that method 1 is better. – Agent 0 Dec 06 '17 at 05:32