Due Tuesday May 20, 1997
Reading: Ford & Topp pages

1 The following array of current size 11 represents a heap structure:

1	2	3	4	5	6	7	8	9	10	11	12
97	76	61	42	54	59	31	23	17	44	49

The tree diagram of this heap is shown below:



a. (5 points) Insert a new value 86 into the heap. Draw the new heap when done. [Increase the heap size from 11 to 12, place 86 initially into slot 12 of the array, then perform upheap to restore the heap conditions.]







b. (10 points) Start again with the original heap of 11 elements. Show the result of each pass of HEAPSORT. Note: After one pass 97 is in position 11 and the values in positions 1 .. 10 again form a heap.

1	2	3	4	5	6	7	8	9	10	11
97	76	61	42	54	59	31	23	17	44	49

2. (5 points) Write a C++ function that takes as input a pointer to the root of a binary tree, and prints the node values of the tree in level order. Assume you have available a Queue Class, to build a queue of node pointers, with the following public member functions:

	// default constructor (makes the empty queue)
	Queue ();
	
	// destructor
	~Queue();
	
	// conditionals: empty? full? - DonŐt worry about full.
	bool IsEmpty ();
	
	// add new item to the queue
	Queue& Enqueue (Node* data);
	
	// remove item from the queue
	Node* Dequeue ();
	};
	

	int PrintRange(Node* root, int low, int high);

Last Updated: May 18, 1997 9:18 am by