CSC300: Homework (Heap Problems, Heaps and Priority Queues)

(Click here for one slide per page)

• Read Algorithms Section 2.4 and Section 2.5.

• Do Quiz 8 on D2L.

• Do the homework assigned on D2L (See Submissions).

  Make sure to submit each file to the correct folder. I will not move your homework to the correct folder (mostly because I won't look closely) - downloading your submissions and autograding them is automated!

  In this homework, you will work with binary heaps and priority queues.

  You may want to do hw7b (the problems from the book) first.

  hw8a: Heaps and Priority Queues

  • Create a new package in IntelliJ IDEA, called ds1.student.pq. Download the following files and save them to this new package.

    • PriorityQueue.java
    • BinaryHeap.java
    • BinaryHeapPQ.java

  • Implement all the functions requested. Follow all instructions!.

    Start with BinaryHeap.java. Then implement BinaryHeapPQ.java using the static utility methods you wrote in BinaryHeap.java. Do not change the interface defined in PriorityQueue.java (or anything within that file)!

  hw7b: Heap Problems

  • Do the following eight problems from the Algorithms text on paper. The starred ones are especially important to understand.

      2.4.2
      2.4.4
      2.4.5
      2.4.9*
      2.4.11
      2.4.12
      2.4.15* 
      2.4.27*