## Lecture 29 - Heaps

As usual, create a directory to hold today's activities:

$mkdir ~/cs170/labs/lab29$ cd ~/cs170/labs/lab29


### Emacs Commands!

C-f
Move the cursor forward
C-b
Move the cursor backward
C-n
Move the cursor to the next line
C-p
Move the cursor to the previous line
C-s
Begin search mode

### Heaps

Heaps are a very special form of a binary tree. Every node has at most 2 children, just like a typical binary tree. It is the order of the elements in the binary tree that changes with a heap. In a binary search tree, the items were arranged in such a way that everything on the left sub-tree was less than or equal to the parent. In a min-heap, ALL children of the parent are greater than their parent node. The real interesting thing about heaps are that we can represent them with a 1-dimensional structure: a python list!

Lab Activity 1
Inserting

The key function behind inserting into a MinHeap is that we have to make sure that the minimum element in the entire list ends up at the $$0^{th}$$ index. The naive approach is to perform one iteration of insertion sort. This is a $$O(n)$$ operation. Which means after inserting every element into the heap we have insertion sort: $$O(n^2)$$. The next approach would be to insert all the elements, and run merge sort: $$O(n \times log(n))$$. However, we might not know all of the data at once.

The better approach would be to treat the list as a tree. If we can figure out an efficient mechanism for bubbling the inserted element to the correct location, maybe we can accomplish this in less than $$O(n)$$ time.

#### Details

Download my copy of heap.py into your lab29 directory. You will add a method called insert(self, data). This should take some data, and insert it into the correct location for a heap.

The process for this is a little confusing. You will append the data to the end of your list, and "bubble" it up to it's correct location. This is done by comparing the data you just inserted to its parent. If the value at the child location is less than the parent location, swap them. Then, move to the parent location and continue the process. You stop the entire process the first time you don't make a swap, or you hit the root.

#### Example

>>> min_heap = MinHeap()
>>> min_heap.insert(5)
>>> print(min_heap)
[5]
>>> min_heap.insert(4)
>>> print(min_heap)
[4, 5]
>>> min_heap.insert(3)
>>> print(min_heap)
[3, 5, 4]
>>> min_heap.insert(2)
>>> print(min_heap)
[2, 3, 4, 5]
>>> min_heap.insert(1)
>>> print(min_heap)
[1, 2, 4, 5, 3]
>>> min_heap.insert(6)
>>> print(min_heap)
[1, 2, 4, 5, 3, 6]


#### Hint

I covered get_parent_index in class today. You will use this to figure out the index of the parent. You simply need to compute the index of the parent, swap them if necessary, and continue the process at the parent index.

### Challenge

This is incredibly straight forward in a list. However, it is much more complicated with an actual tree structure. Notice I said more complicated, and not impossible.

Copy your binary tree class from Friday into your directory. Add a function called insert_heap(self, data), which takes data and adds it in the correct location for a heap insertion.

Hint: Perform a breadth-first search to find the location to insert the node at initially. This will be the first missing child of a node. Then, swap the data from the nodes to bubble up. Swapping actual nodes becomes incredibly complex.

Lab Activity 2
Deleting

Once you have insert finished, finding the minimum element is easy! It's at the root of the tree! However, deleting the minimum element comes with a price...we now need to bubble something up to the root. Again, the naive approach is to just resort the list. But, the fastest time we know of to perform that is $$O(n \times log(n))$$. That seems pretty slow, considering how quick insertion became.

Maybe we could replicate that insertion code here? Except, instead of starting at the bottom and working our way up, we simply start at the top, and work our way down to the leaves.

#### Details

Add a method called delete_min(self). This method simply deletes the minimum item from the list, restructures the list into heap order, and returns the item it deleted from the heap.

In this process, you copy the last value in the tree into the root. Then, starting at the root of the tree, you pick the smallest of the two children. If that child is smaller, then you swap that value into the the parent. If you didn't swap, then you are done. If you did swap, you then need to perform the same process at the location you swapped the parent into.

#### Example

>>> min_heap = MinHeap()
>>> for i in range(5, -1, -1):
...     min_heap.insert(i)
>>> print(min_heap)
[0, 2, 1, 5, 3, 4]
>>> while min_heap.size() > 0:
...     print(min_heap.delete_min())
...     print(min_heap)
0
[1, 2, 4, 5, 3]
1
[2, 3, 4, 5]
2
[3, 5, 4]
3
[4, 5]
4
[5]
5
[]


#### Hint

This function will use the get_child_index method I discussed in class. You might be able to simplify your delete method by also writing a get_min_child_index, which gives you the index of the child with the smallest value.

If the value of the min child is less than the parent, then swap the values between the two in the list. You will want to keep a boolean variable to keep track of whether you have performed this swap. If you didn't perform the swap, you are done.

### Challenge

Again, this is a little more complicated using a real binary tree structure. But it is definitely within your capabilities. Add a delete_min method to the same class as the prevous challenge. It should behave much the same as the list version, but on a real list structure.

#### Submission

When you have finished, create a tar file of your lab29 directory. To create a tar file, execute the following commands:

cd ~/cs170/labs
tar czvf lab29.tgz lab29/


To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Lab Assignment 29. Make sure you include a header listing the authors of the file.