Data Structures and Algorithms in Java
GitHubAuthor
  • Preface
    • Syllabus
    • Schedule
  • 0. Getting Started
    • 0.1. Environment Setup
    • 0.2. Quiz
  • 1. Java Essentials
    • 1.1. Abstraction
    • 1.2. Implementation
    • 1.3. Unit Testing
    • 1.4. Quiz
  • 2. Priority Queues
    • 2.1. Simple Priority Queues
    • 2.2. Binary Heap
    • 2.3. Unit Testing
    • 2.4. Benchmarking
    • 2.5. Quiz
  • 3. Sorting Algorithms
    • 3.1. Abstraction
    • 3.2. Comparison-based Sort
    • 3.3. Divide & Conquer Sort
    • 3.4. Distribution-based Sort
    • 3.5. Quiz
    • 3.6. Homework
  • 4. Binary Search Trees
    • 4.1. Binary Search Trees
    • 4.2. Balanced BST
    • 4.2. AVL Trees
    • 4.3. Red-Black Trees
    • 4.4. Quiz
  • 5. Tries
    • 5.1. Concept
    • 5.2. Implementation
    • 5.3. Quiz
    • 5.4. Homework
  • 6. Disjoint Sets
    • 6.1. Concept
    • 6.2. Implementation
    • 6.3. Quiz
  • 7. Graphs
    • 7.1. Implementation
    • 7.2. Cycle Detection
    • 7.3. Topological Sorting
    • 7.4. Quiz
  • 8. Minimum Spanning Trees
    • 8.1. Abstraction
    • 8.2. Prim's Algorithm
    • 8.3. Kruskal’s Algorithm
    • 8.4. Edmonds' Algorithm
    • 8.5. Quiz
    • 8.6. Homework
  • 9. Network Flow
    • 9.1. Flow Network
    • 9.2. Ford-Fulkerson Algorithm
    • 9.3. Simplex Algorithm
    • 9.3. Quiz
  • 10. Dynamic Programming
    • 10.1. Fibonacci Sequence
    • 10.2. Tower of Hanoi
    • 10.3. Longest Common Subsequence
    • 10.4. Quiz
Powered by GitBook

©2023 Emory University - All rights reserved

On this page
  • Abstract Priority Queue
  • Lazy Priority Queue
  • Eager Priority Queues

Was this helpful?

Export as PDF
  1. 2. Priority Queues

2.1. Simple Priority Queues

Lazy and eager priority queues.

Previous2. Priority QueuesNext2.2. Binary Heap

Last updated 2 years ago

Was this helpful?

A priority queue (PQ) is a data structure that supports the following two operations:

  • add(): adds a comparable key to the PQ.

  • remove(): removes the key with the highest (or lowest) priority in the PQ.

A PQ that removes the key with the highest priority is called a maximum PQ (max-PQ), and with the lowest priority is called a minimum PQ (min-PQ).

Does a priority queue need to be sorted at all time to support those two operations? What are the use cases of priority queues?

Abstract Priority Queue

Let us define that is an abstract class to be inherited by all priority queues:

public abstract class AbstractPriorityQueue<T extends Comparable<T>> {
    protected final Comparator<T> priority;

    /**
     * Initializes this PQ as either a maximum or minimum PQ.
     * @param priority if {@link Comparator#naturalOrder()}, this is a max PQ;
     *                 if {@link Comparator#reverseOrder()}, this is a min PQ.
     */
    public AbstractPriorityQueue(Comparator<T> priority) {
        this.priority = priority;
    }
}
  • L2: is a comparator that can compare keys of the generic type T.

    • final: must be initialized in every constructor.

  • L6: the javadoc {@link} hyperlinks to the specified methods.

What are comparable data types in Java? Can you define your own comparator?

Let us define three abstract methods, add(), remove(), and size() in AbstractPriorityQueue:

/**
 * Adds a comparable key to this PQ.
 * @param key the key to be added.
 */
abstract public void add(T key);

/**
 * Removes the key with the highest/lowest priority if exists.
 * @return the key with the highest/lowest priority if exists; otherwise, null.
 */
abstract public T remove();

/** @return the size of this PQ. */
abstract public int size();

Given the abstract methods, we can define the regular method isEmpty():

/** @return true if this PQ is empty; otherwise, false. */
public boolean isEmpty() {
    return size() == 0;
}

Lazy Priority Queue

  • add(): takesO(1)O(1)O(1)to add a key to the PQ.

  • remove(): takesO(n)O(n)O(n) to remove the key with the highest/lowest priority from the PQ.

In other words, all the hard work is done at the last minute when it needs to remove the key.

public class LazyPriorityQueue<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
    private final List<T> keys;

    /** Initializes this as a maximum PQ. */
    public LazyPriorityQueue() {
        this(Comparator.naturalOrder());
    }

    /** @see AbstractPriorityQueue#AbstractPriorityQueue(Comparator). */
    public LazyPriorityQueue(Comparator<T> priority) {
        super(priority);
        keys = new ArrayList<>();
    }
    
    
    @Override
    public int size() {
        return keys.size();
    }
}
  • L1: declares T and passes it to its super class, AbstractPriorityQueue.

  • L2: defines a list to store input keys.

  • L17-19: overrides the size() method.

Can you add keys to the member field keys when it is declared as final (a constant)? Why does all constructors in LazyPriorityQueue need to call the super constructor?

We then override the core methods, add() and remove():

/**
 * Appends a key to {@link #keys}.
 * @param key the key to be added.
 */
@Override
public void add(T key) {
    keys.add(key);
}

/**
 * Finds the key with the highest/lowest priority, and removes it from {@link #keys}.
 * @return the key with the highest/lowest priority if exists; otherwise, null.
 */
@Override
public T remove() {
    if (isEmpty()) return null;
    T max = Collections.max(keys, priority);
    keys.remove(max);
    return max;
}
  • L6-8: appends a key to the list in O(1)O(1)O(1).

  • L15-20: removes a key to the list in O(n)O(n)O(n).

    • L16: edge case handling.

    • L18: removes a key from the list in O(n+n)=O(n)O(n+n) = O(n)O(n+n)=O(n).

Is ArrayList the best implementation of List for LazyPriorityQueue? Why does remove() in L18 cost O(n+n)O(n+n)O(n+n)?

Eager Priority Queues

  • add(): takesO(n)O(n)O(n)to add a key to the PQ.

  • remove(): takesO(1)O(1)O(1) to remove the key with the highest/lowest priority from the PQ.

In other words, all the hard work is done as soon as a key is added.

What are the situations that LazyPQ is preferred over EagerPQ and vice versa?

public class EagerPriorityQueue<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
    private final List<T> keys;

    public EagerPriorityQueue() {
        this(Comparator.naturalOrder());
    }

    public EagerPriorityQueue(Comparator<T> priority) {
        super(priority);
        keys = new ArrayList<>();
    }
    
    @Override
    public int size() {
        return keys.size();
    }
}
  • The implementations of the two constructors and the size() method are identical to the ones in LazyPriorityQueue.

Should we create an abstract class that implements the above code and make it as a super class of LazyPQ and EagerPQ? What level of abstraction is appropriate in object-oriented programming?

We then override the core methods, add() and remove():

/**
 * Adds a key to {@link #keys} by the priority.
 * @param key the key to be added.
 */
@Override
public void add(T key) {
    // binary search (if not found, index < 0)
    int index = Collections.binarySearch(keys, key, priority);
    // if not found, the appropriate index is {@code -(index +1)}
    if (index < 0) index = -(index + 1);
    keys.add(index, key);
}

/**
 * Remove the last key in the list.
 * @return the key with the highest priority if exists; otherwise, {@code null}.
 */
@Override
public T remove() {
    return isEmpty() ? null : keys.remove(keys.size() - 1);
}
  • L6-12: inserts a key to the list in O(n)O(n)O(n) .

    • L8: finds the index of the key to be inserted in the list using binary search in O(log⁡n)O(\log n)O(logn).

    • L11: inserts the key at the index position in O(n)O(n)O(n).

  • L19-21: removes a key from the list in O(1)O(1)O(1).

What are the worst-case complexities of add() and remove() in LazyPQ and EagerPQ in terms of assignments and comparison?

L1: declares the type T that is the type of input keys to be stored in this PQ.

T must be by its priority.

Comparators: , .

Let us define whose core methods satisfy the following conditions:

L17: finds the max-key in the list using in O(n)O(n)O(n).

Let us define whose core methods satisfy the following conditions:

L10: reverse engineers the return value of .

AbstractPriorityQueue
generic
comparable
naturalOrder()
reverseOrder()
LazyPriorityQueue
Collections.max()
EagerPriorityQueue
Collections.binarySearch()