CSC 402

Winter 2015

Craig Miller

• Home
• Basic Information
• Grades and Policies
• Schedule

Weekly Notes

• Week 1
• Week 2
• Week 3
• Week 4
• Week 5
• Week 6
• Week 7
• Week 8
• Week 9
• Week 10

Assignments

• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4
• Midterm
• Assignment 5
• Assignment 6
• Assignment 7

Assignment 7
Priority Queues and Heaps
Submit before 11:30 PM Saturday March 14

Overview

This assignment involves working with a heap, an efficient data structure for implementing priority queues.

Problems

1. For each of the following sequences of float values, indicate whether they form and array-based min-heap, max-heap or no heap:
   1. 4.3 2.1 2.3 1.1 1.9 2.2
   2. 2.3 5.3 4.1 4.7 4.9 7.8
   3. 5.7 4.3 4.7 3.0 3.3 4.5 4.6 1.1 2.0 3.1
   4. 2.3 4.1 5.3 6.7 6.0 5.9 5.4 7.3 7.0 8.3 7.4 6.1
   5. 7.4 5.3 5.5 4.3 5.1 5.4
2. For each of the following sequences of float values, produce the min-heap array that would result if they were inserted in the order that they appear below:
   1. 5.4 4.3 6.7 1.2 4.5 7.2 1.1
   2. 3.4 4.3 1.8 1.3 1.9 1.1
3. Consider the follow array-based min-heap: 1.3 2.7 2.1 3.2 3.1 6.8 6.7 4.8 5.9 8.3. Produce the min-heap array that would result by removing the minimal element from the heap.
4. Write a class called HeapCheck that has a method that takes an array of float values and indicates whether the array represents a min-heap, a max-heap or no heap. If all values are the same, your code may simply indicate that it's a min-heap. Your main method should demonstrate that your code works correctly.

Submission

Submit a zipped folder that includes the written answers (any common format is fine) and the code in a package named "assn7".