Building a Heap

Heap Data Structure

Recall from class that a heap is a binary tree that maintains two properties:

1. The tree is a complete binary tree (where all the leaves are in the bottom two depths and are filled in from left-to-right), and

2. Parents and their children follow the min heap-order property where every parent is less than or equal to its children

The second property insures that the minimum value in a heap is always the root (and the second smallest is one of its children), and the first property allows us to represent the binary tree as an array where the values in the nodes are stored in the array from left to right – first the root node, then the next depth from left to right, etc. Here is our example heap from lecture as both a binary tree and array:

Practicing Inserting Items into a Heap

Imagine that you are given the data:

[2, 8, 13, 34, 21, 5, 55, 1, 89, 144, 3]

Create a heap by inserting these numbers in the order listed – first 2, then 8, then 13, etc. until you lastly insert 3. After inserting every number, draw the heap as both a binary tree and an array. The pseudocode for the insert and percolateUp operations are provided in both the class slides and Part 2 of the lab. Upload your drawing (if you draw by hand, you can take a picture with a phone) to your GitHub repository.

Practice Removing Items from a Heap

Next, remove the minimum item from the heap, then draw the new contents/structure of the heap as both a binary tree and an array. The pseudocode for the remove and percolateDown operations are provided in both the class slides and Part 3 of the lab. Upload this second drawing in a second image file in your GitHub repository. Do not forget to add/commit/push your image files.