Winard Ronald Britt - COMP 3270 Homework 1

Binary Heap Insert Algorithm

What is a Binary Heap?

It is a data structure designed to keep up with a maximum or minimum value of interest, to return that value of interest, and to be able to have efficient inserts and deletions in that structure. This has a variety of applications, including priority queues and efficient sorting algorithms (Heap Sort).

More technically, it is a complete binary tree where every node is either less than (Max Heap) or greater than (Min Heap) its parent. This property is called the Heap Property.

How do we implement it?

Since the tree is always complete, we can implement this data structure efficiently with an array structure (no wasted space like in, say, an unbalanced binary tree).

The root of the binary heap (and consequently the Min or Max value) is always in the Array index 1.

If a node is at Array[i], then its parent will be the floor of i/2 (to get the "floor" you simply divide, then truncate the fraction). Its left child will be at Array[2*i] and its right child will be at Array[2*i + 1]

Here is the conceptual model of a Min Heap.

Here is the corresponding array implementation of the above Min Heap.

How do we insert a new value into a Binary Heap?

Let’s use a Min Heap for our example. Intuitively, we want to find a hole (after the last element in the array), place the new element in it, then move or "percolate" it up the tree by swapping it with its parents until we find a place for it that preserves the heap property.

Let’s look at the algorithm:

Procedure Insert (x, H)
* // We need the node to insert (x) and the Heap into which to insert it (H)
Begin
      if Is-full (H) then raise-exception “heap full” end if
//Since we are using an array-based implementation, we must be careful about the array size
      Hsize = Hsize + 1
//Increase the size value since we are adding a value
      I = Hsize
//We are going to start looking for a place to put x in the first available space (the last
//index in the array in order to preserve the Complete Binary Tree structure. If this
//place also fulfills the Heap Property, then we can stop.
      while I > 1 and H[1/2] > x loop
//If the parent is larger than x, we need to move x up in the heap or “percolate” it up.
//If I < 1, it has become the root and we cannot and should not attempt to move it further.
            H[I] = H[1/2]
            I = I/2
//We are moving the parent down to fill the hole and then moving our prospective node up one level
      End while
      H[I] = x
//When the while loop exits, we have found a hole that preserves the Heap Property.
//Now we set the hole we have found to the value of x.
End Insert

Want to see it in action?

Interactive Data Structure Visualizations

Follow the above link and enter your name (it doesn’t matter) and then click on “Priority Queue” on the left menu. Next, you will need to click on the “Start Visualization” button located at the bottom right of the window. Give the visualization a moment to load. Please, interact with this Algorithm Animation and follow through several Enqueues. I would advise stepping through the Algorithm (“Single Step” option instead of the “Continuous” option) the first few times to make sure you understand. Try to guess what the next step is before stepping. Once you are confident, change the option from “Show Me” to “I’ll try.” When you are done, click on “Stop Visualization” at the bottom to close out the window.

Efficiency

Since the algorithm will, in the worst case, have to move a node all the way from the point of insertion to the root itself, it may run no more than the height (h) times. Since this is a complete binary tree, h will be equal to the log(n). Since the operations are all in constant O(1) time, the total running time is O(log n).

Auburn University, Alabama

The explanations on this page and the images were created by Winard Britt. Credit for the contained links goes to their respective creators.

Auburn University Home Page