$ mkdir ~/cs170/labs/lab30 $ cd ~/cs170/labs/lab30
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 less than their parent node. The real interesting thing about heaps are that we can represent them with a 1-dimensional structure: a python list!
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 0th 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(n2). The next approach would be to insert all the elements, and run merge sort: O(n 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 the inserted element to the correct location, maybe we can accomplish this in less than O(n) time.
Download my copy of heap.py
into your lecture30 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. Otherwise, move to the parent location and continue the process until you hit the root.
>>> 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]
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.
This is incredibly straight forward in a list. However, it is much more complicated with an actual tree structure. Notice I said , and not impossible.
Copy your binary tree class from Wednesday 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.
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 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.
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 start at the root of the tree. You pick the smallest of the two children, and move it up to the root. Then, you move to the sub-tree that you just copied the data out of, and re-run this process again. You do this until your parent is a leaf of the tree.
>>> 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 []
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.
You actually don't have to perform any swaps here. You can simply assign the value to the parent location, since it is a duplicate copy of something else in the list.
When you are done, you need to pop the list, using the index of the last child you copied from.
Again, this is a little more complicated using a real binary tree
structre. 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.
When you have finished, create a tar file of your lab30
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab30.tgz lab30/
To submit your activity, go to cseval.roanoke.edu. You should
see an available assignment called Lab Assignment 30.
Make sure you include a header listing the authors of the file.