UCR CS 14: Introduction to Data Structures and Algorithms

Spring Quarter 2003 / Class webpage

Lab 08

Remember:

• All programming assignments will be done under the Linux operating system, using standard programming tools for that environment.
• All programming assignments will be evaluated with the -Wall -Werror compilation options. If your program does not compile with these flags, it will not be evaluated.
• Concentrate some effort on style and documentation. A significant portion of your grade will be based on these aspects of your submission.
• You have to turnin your codes before you leave.
• Every part of your assignment (every file) must begin with our report template header:

// Course:            CS 14

// Lecture Section:   Enter your lecture section number here (1, 2, etc)
// Lab Section:       Enter your lab section number here (21, 22, etc)
// Assignment #:      Enter the assignment number here (1, 2, etc)

// First Name:        Enter your FIRST name here (eg, John)
// Last Name:         Enter your LAST name here (eg, Doe)
// ID Number:         Enter your ID number here (eg, 12-345-678)
// Email address:     Enter your UCR email address here (eg, jdoe@cs.ucr.edu)

// ===============================================================

In this lab, we will work with ADT Heap (chapter 11). A heap is a complete binary tree:
   1.That is empty
or
   2a. Whose root contains a search key greater than or equal to the search key in each of its children, and
   2b. Whose root has heaps as its subtrees.

In this lab you will work using an array-based implementation of the ADT heap. You will need the following files:

• Heap.h - ADT heap header.
• Heap.cc - ADT heap implementation.
• HeapException.h - heap exception handler.
• KeyedItem.h - KeyedItem header.
• lab8.cc - program that reads values from keyboard and stores them in a heap.
• makefile

Figure 1. UML diagram for the class Heap

In our definition of a heap, the root contains the item with the largest search key. Such a heap is also known as a maxheap. A minheap, on the other hand, places the item with the smallest search key in its root. Today you will implement a minheap and trace the swaps necessary for inserting new values in the heap, for example:

Enter a positive value (negative value to stop): 6
Insert value: 6
Heap values:
6

Enter a positive value (negative value to stop): 8
Insert value: 8
Heap values:
6  8

Enter a positive value (negative value to stop): 7
Insert value: 7
Heap values:
6  8  7

Enter a positive value (negative value to stop): 5
Insert value: 5
    (1) Swap 5 and 8
    (2) Swap 5 and 6
Heap values:
5  6  7  8

Enter a positive value (negative value to stop): 4
Insert value: 4
    (3) Swap 4 and 6
    (4) Swap 4 and 5
Heap values:
4  5  7  8  6

Enter a positive value (negative value to stop): 2
Insert value: 2
    (5) Swap 2 and 7
    (6) Swap 2 and 4
Heap values:
2  5  4  8  6  7

Enter a positive value (negative value to stop): -1

Figure 2 illustrates these insertions.

Figure 2. Sequence of insertions in a heap

Even though you do not have enough time to finish all bonus exercises during the lab, you should try to do them by yourself. Keep in mind that only those exercises that you turn in during the lab will be considered in your grade.

Turn-in

Implement a minheap such that your program prints the following information for each insertion:

• New value (which you are inserting).
• Number of swap.
• Values that the program is swapping.
• New heap after the insertion.

You may use the ADT maxheap available in the files cited above. Feel free to come up with your own implementation, just keep in mind that the file names must be Heap.h, Heap.cc, and lab8.cc.

Interesting question: does the order in which you insert items into a heap affect the heap that results? Run some experiments to support your idea.

Bonus, 2 points each

a) Add the delete option in your main program such that after inserting all values, the user may start delete values. Besides the value, number of swap, and values that the program is swapping, show the heap before and after rebuilding it. For example:



Enter a positive value (negative value to stop): 6 Insert value: 6 Heap values: 6 Enter a positive value (negative value to stop): 8 Insert value: 8 Heap values: 6 8 Enter a positive value (negative value to stop): 7 Insert value: 7 Heap values: 6 8 7 Enter a positive value (negative value to stop): 5 Insert value: 5 (1) Swap 5 and 8 (2) Swap 5 and 6 Heap values: 5 6 7 8 Enter a positive value (negative value to stop): 4 Insert value: 4 (3) Swap 4 and 6 (4) Swap 4 and 5 Heap values: 4 5 7 8 6 Enter a positive value (negative value to stop): 2 Insert value: 2 (5) Swap 2 and 7 (6) Swap 2 and 4 Heap values: 2 5 4 8 6 7 Enter a positive value (negative value to stop): -1 ----------------------------------------------------- Now you may DELETE some nodes. Do you want to delete the root? (y / n)? y Delete value: 2 Heap values: 7 5 4 8 6 (1) Swap 7 and 4 Heap values: 4 5 7 8 6 Do you want to delete the root (y / n)? y Delete value: 4 Heap values: 6 5 7 8 (2) Swap 6 and 5 Heap values: 5 6 7 8 Do you want to delete the root (y / n)? y Delete value: 5 Heap values: 8 6 7 (3) Swap 8 and 6 Heap values: 6 8 7 Do you want to delete the root (y / n)? n

b) This implementation of heap uses two swaps:

• In the function heapInsert.

HeapItemType temp = items[parent];
items[parent] = items[place];
items[place] = temp;

• In the function heapRebuild.

  HeapItemType temp = items[root];
  items[root] = items[child];
  items[child] = temp;

Implement another ADT heap (called Heap2) in which those swaps are unnecessary.
Note 1: keep the same functions and structure presented in Heap.
Note 2: the ADT heap we provide is an array-based implementation. You should consider another kind of implementation in this bonus part.