$ mkdir ~/cs170/labs/lab29 $ cd ~/cs170/labs/lab29
C-f
C-b
C-n
C-p
C-s
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!
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 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 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.
>>> 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 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.
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.
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.
>>> 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.
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.
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.
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.