In this lab, we see another structure that can be used to implement a priority queue: the heap. A heap is a kind of tree that offers both insertion and deletion in O(log N) time.
At the end of this lab, you need to submit a word document including some text answers and screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start->All Programs->Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).
Operations on Heap.html
(1.) Click Start > Windows System -> Command Prompt. Use command "cd" to move into the directory where you run the applet, such as cd C:\COSC3333\Chap12\Heap. Then use the command appletviewer Heap.html to run the application, see Figure 1. Fig. 1 Initial State for a Heap
(2.) Fill 10 in the blank of Enter number, and click Fill to randomly initialize a 10 elements heap, we have Figure 2 (your tree may be different since the numbers are randomly selected, maximally it could have 31 nodes in 5 levels). Q1: Where is the location of the maximum key in heap? Fig. 2 A Random 10-element Heap
(3.) Click Ins to insert 31, 97, 56, we have Figure 3 after all elements are inserted. Q2: What is the insertion process of a heap? Fig. 3 Insert Elements 31, 97, 56
(4.) Fill 28 in Enter number. Click on the left child of the root (in my case it is 75) to select it, and click Chng button again to change the key value. Figure is shown in Figure 4. Q3: What happens next in heap to keep the characteristics of the heap? Which child it selects to trickle down? Why? Try to do it again by replacing the right child of the root (in my case it is 77) with 18, see Figure 5. Fig. 4 Change Left Child of Root with 28 Fig. 5 Change Right Child of Root with 18
(5.) Click Rem to observe the remove process, see Figure 6. Q4: What is remove process? Can any node be removed from Heap? Fig. 6 Remove Operation of a Heap
Part I: Answer the questions:
Q1: Where is the location of the maximum key in heap?
Q2: What is the insertion process of a heap?
Q3: What happens next in heap to keep the characteristics of the heap? Which child it selects to trickle down? Why?
Q4: What is remove process? Can any node be removed from Heap?
Part II: Screen shots
Submit the screenshots for Figure 2 to Figure 6 (totally 5 figures) through Blackboard. (Don't forget to include your name in the program). (At the end of this lab, you need to submit a word document including some screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start->All Programs- >Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).