1
h09
CS24 W18
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu section
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h09: Heaps: Chapter 11.1 and 11.2

ready? assigned due points
true Tue 05/29 11:00AM Tue 06/05 11:00AM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE/LAB LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the three lowest scores (if you have zeros, those are the three lowest scores.)

Please:

  • No Staples.
  • No Paperclips.
  • No folded down corners.

Please read chapters 11.1 and 11.2 of the book on Heaps and Priorty Queues (If you don’t have a copy of the textbook yet, there is one on reserve at the library under “COMP000-STAFF - Permanent Reserve”).

    1. (10 pts) Contrast a heap with a binary search tree by inserting the numbers 60, 30, 40, 50, 20, 10 first in a BST and then in a min-heap. Draw the resulting BST on the left and the heap on the right. You may draw any valid BST or Heap that contain the provided values.
    2. (5 pts) In section 11.1, the book mentions that heaps are **complete** binary trees, what does that mean? Demonstrate by drawing an example of a binary tree with 5 nodes that is not complete and one that is complete.
    3. (5 pts) Section 11.1 mentions that complete binary trees can be implemented using arrays. Provide the array representation of the heap that you constructed in Q1 containing the key values: 60, 30, 40, 50, 20, 10
    4. (10 pts) Insert the value 5 into the heap from Q3. Show how the original binary heap tree is modified on an insertion. Show also how the array representation of the heap is modfied to insert the new value.
    5. (10 pts) Starting with the heap from Q3, delete the value 10 from the heap. Show how the original binary heap tree is modified on a deleting. Show also how the array representation of the heap is modfied when deleting the value.
    6. (10 pts) Compare the Big -O running time of min, max, insert, delete and search for the following data structures: sorted array, generic BST, balanced BST, min-Heap, linked-list (unsorted), stack and queue