Heap Insertion

Let's talk about how to insert items into a heap. To do so, let's define a Heap class that we can add functionality to, and start it with a list of items and a counter for the current number of items:

class Heap:
    def __init__():
        self.contents = []
        self.num_items = 0

Recall that since heaps are complete trees, they have a convenient representation as a list. Therefore, we'll avoid creating a linked data structure and instead implement the heap using a list.

Algorithm

Watch the video below to see how to insert an item into a heap:

To summarize:

• The new item initially gets put into the end of the list (a leaf node).
• The value in that leaf node is "sifted up" in the heap until it obeys the heap property.

Efficiency

When inserting an item into the heap, we first place the item in the last position in the list in constant time. However, we then need to run the sift_up() algorithm, which in the worst case pushes the item from a leaf node all the way up to the root.

Since the heap is a complete tree, we know that it is also balanced, and therefore we can say that in the worst case, an item is sifted up throughout the height of the tree, where h = O(logn). Each of the swaps that occurs during the sift operation takes constant time.

Therefore, insertion in a heap is O(logn).

Now that we know how to insert items into a heap, let's take a step back and look at the overall heap constructoin algorithm and its efficiency. The big-O notation for building a heap may surprise you!