In this chapter, we will take a look at some more interesting data structures that are commonly used. We will start with the concept of a priority queue. We will see some efficient implementations of a priority queue. In short, we will cover the following topics in this chapter:
- Priority queue ADT
- Heap
- Binomial forest
- Sorting using a priority queue and heap
A priority queue is like a queue in that you can enqueue and dequeue elements. However, the element that gets dequeued is the one with the minimum value of a feature, called its priority. We will use a comparator to compare elements and learn which one has the lowest priority. We will use the following interface for the priority queue:
public interface PriorityQueue<E> {
E checkMinimum();
E dequeueMinimum();
void enqueue(E value);
}We require the following set of behaviors from the methods:
checkMinimum: This method must return the next value to be dequeued without dequeuing it. If the queue is empty, it must return null.dequeueMinimum: This must dequeue the element with the minimum priority and return it. It should return null when the queue is empty.enqueue: This should insert a new element in the priority queue.
We would also like to do these operations as efficiently as possible. We will see two different ways to implement it.