CSE 247 Module 3: Priority Queues

Studio


Bad Priority Queue Implementations
Authors: Tim Heyer and Ron Cytron

Introduction

In lecture, you've learned several different data structures that can be used to implement a priority queue and the pros/cons for each. In this studio, you will implement two of these priority queues and examine where each shines over the other.
For reference, you can review the lecture slides on
  1. As always, do a TeamPull to update your repository.
  2. Begin by opening the studio3 package in the studios source folder of your repository.
  3. Find and open PriorityQueue.java and examine the interface.
    Part A

    As before, answer the following questions in the studio3.txt file in your studiowriteups folder:

    • Look at the Comparable interface.
    • Name three data types that could serve as T.
    • Find a class there that you don't know yet, and visit it to see how it implements compareTo(…).

      To find the source code, Google the name of the class along with the words source code and that should take you to a page with the Java code for that class. For example, you already know String, so you can't pick that one, but if you Googled this, and picked the top hit, it would show you the source code. From there, you can click on the compareTo method to see its code.

  4. The compareTo(…) method is of great interest for this and subsequent assignments. Given the call a.compareTo(b), which of the following is true?
    Part B: Discuss this among yourselves and your TA. Write your answers into studio3.txt.
  5. Open the UnorderedList.java class, complete the methods, and run the associated unit test in the studio3.test package.
    Here, you are using Java's built-in LinkedList implementation. This implementation is different from what we have done in class, but you don't need to worry about how it is different. You can use its API however you want, but use one of its methods to add a new item into your list, which represents the priority queue.

    There is no order here, so it doesn't matter where the new item goes.

  6. Even if you don't understand exactly how LinkedList works, you can discover much about the complexity of an operation by looking at its source code.

    Take a look at this source code and answer the following questions. You have to click on links to method calls to get to their source. As you go, determine whether the result of calling the method to add an object to the list takes constant time, or time that depends on the current size of the list.

    Part C

    From your inspection of the LinkedList class's source code: Given a LinkedList of size n, what is the asymptotic complexity, worst-case, for performing each of the following operations?

    1) Appending to the end of that list addLast(Objct)

    2) Prepending to the beginning of that list addFirst(Object)

    3) Inserting an element in the middle of the list add(int, Object)

    And for your implementation of a PriorityQueue using the Unordered List, given n elements already in the queue, what is the asymptotic complexity, worst-case for performing each of the following operations?

    4) extractMin

    5) insert

    6) isEmpty

  7. Open the OrderedArray.java class, complete the methods, and run the unit tests.
    Assume that the initial size of the array, established in the constructor, is sufficiently large to accommodate any number of inserts called on the class.
    Part D

    From your implementation of OrderedArray, what is the asymptotic complexity, worst-case, for performing each of the following operations?

    1) Adding an element at the end of the array

    2) Inserting an element at the beginning of the array

    3) Inserting an element in the middle of the list

    And for your implementation of a PriorityQueue using the Ordered Array, given n elements already in the queue, what is the asymptotic complexity, worst-case for performing each of the following operations?

    4) extractMin

    5) insert

    6) isEmpty

    Are there situations when you would want to use the OrderedArray or the UnorderedList instead of the binary heap described in class? Explain please.


Submitting your work (read carefully)



Last modified 14:54:19 CDT 31 October 2016
When you done with this studio, you must be cleared by the TA to receive credit.

This demo box is for studio 3
Last name WUSTL Key Propagate?
(NOT your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others
3 Copy from 3 to all others
4 Copy from 4 to all others

TA: Password: