Studio 3: Bad Priority Queue Implementations

Introduction

Last week and this week, we saw several different data structures that can be used to implement the priority queue (hereafter, "PQ") abstract data type. Which structure we choose has a significant impact on the performance of the PQ operations. This week, you will actually code some of these alternatives and investigate their performance.

Part A: Comparing Objects in Java

  • Go to the studio3 package in your repository, and open PriorityQueue.java.

Did you to remember to do a Team/Pull operation first?

PQs hold values that can be totally ordered; otherwise, it would make no sense to ask for the minimum or maximum value. For this reason, the type T of the PQ's element must implement the Java Comparable interface, which allows you to query this total ordering for any pair of objects of type T.

  • Read through the description of the Comparable interface.

Question A1: Name at least three common data types that could satisfy the properties of Comparable. Include at least one non-numeric data type!

The key method implemented by Comparable is compareTo(), which compares two objects.

  • Read the documentation for the compareTo() method.

Question A2: What do you get if you call a.compareTo(b) when the values of a and b are as follows?

1) a = 1, b = 5
2) a = 3.14159269, b = 2.7182818
3) a = "Hello world!", b = "goodbye, world!"
4) a = 357, b = 357

If you feel the question is ambiguous, explain what ordering you are assuming for the two objects.

There are many different kinds of comparable objects. Some, like integers, have an obvious total ordering. For others, the ordering is more complex.

Question A3: Look at the (very long) list of Java classes that implement the Comparable interface, and pick one that you have never heard of. Read the documentation and explain what it means for one object of this class to be "less than" another.

If the documentation does not make clear what ordering means for your class of interest, you can go read the source code. To find the code for class className, try doing a Google search using the terms

Java className source code

and see what comes back. If you have multiple choices, a good one is official OpenJDK sources from hg.openjdk.java.net. For example, here is the OpenJDK source code for the String class.
(Use a class other than String when answering Question A2.)

Part B: Using Linked Lists for Priority Queues

You're now going to try some of the simple PQ implementations we discussed in class earlier in the week. The first implementation we'll look at uses an unordered linked list.

  • Open the UnorderedList.java class and complete the PQ methods you find there. When you think you've got them right, see if your code passes the associated unit test in the studio3.test package.

This class uses Java's built-in LinkedList class to implement a linked list that stores the contents of the PQ. You can use the LinkedList API however you want, but you should probably use one of its methods to add a new item into your list, which represents the priority queue. The list is unordered, so you can put the new item wherever you want.

Once you've gotten your PQ working, you should think about its efficiency. To determine the cost of the list operations you call, you may need to check the source code of the LinkedList class. source code. Be patient -- you may have to trace through several levels of subroutine calls to find the actual list traversal code.

  • Answer the following questions with respect to the implementation of LinkedList referenced above, which is from OpenJDK version 10:

Question B1: What is the worst-case asymptotic complexity of the following operations on a LinkedList object holding $n$ elements?

  1. Appending to the end of the list: addLast(Object)
  2. Prepending to the beginning of the list: addFirst(Object)
  3. Inserting an element in the middle of the list: add(int, Object)

Question B2: Given how you used LinkList to implement your PQ class, what is the worst-case asymptotic complexity of the following operations on a PQ object holding $n$ elements?

  1. determining if the PQ is empty: isEmpty()
  2. inserting an object: insert(T)
  3. extracting the minimum: extractMin()

Part C: Using Ordered Arrays for Priority Queues

An alternative implementation of a PQ uses an ordered (i.e. sorted) array.

  • Open the OrderedArray.java class and complete the PQ methods you find there. When you think you've got them right, see if your code passes the associated unit test in the studio3.test package.

For this studio, we'll assume that we allocate our array large enough to accommodate the maximum number of items that can be in the PQ at any one time. If there is no room to insert an item, feel free to crash or do whatever you like. A "production-quality" implementation would grow the array if more space was needed... but a production-quality implementation probably would not use an ordered array for the PQ.

Once you've gotten your PQ working, you should again think about its efficiency.

  • Answer the following questions:

Question C1: What is the worst-case asymptotic complexity of the following operations on an OrderedArray object holding $n$ elements?

  1. Appending to the end of the array: addLast(Object)
  2. Prepending to the beginning of the array: addFirst(Object)
  3. Inserting an element in the middle of the array: add(int, Object)

Question C2: Given how you used OrderedArray to implement your PQ class, what is the worst-case asymptotic complexity of the following operations on a PQ object holding $n$ elements?

  1. determining if the PQ is empty: isEmpty()
  2. inserting an object: insert(T)
  3. extracting the minimum: extractMin()

Question C3: Can you think of situations in which you might want to use the OrderedArray or the UnorderedList implementation instead of the binary heap implementation described in class? If so, please explain.