1
h09
CS24 F19
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 Mon 11/25 12:00AM Mon 12/02 11:59PM

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

INSTEAD OF TURNING IN THIS HOMEWORK, YOU WILL TAKE A QUIZ ON GAUCHOSPACE BY THE DUE DATE.
There is NO MAKEUP for missed homework assignments.
The quiz will be made available at least two days before the due date.

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