Priority Queue - Intro

Video #1 within the Priority Queue Series

Transcript:
The priority queue is a data structure built into Java.

The priority queue works like a normal queue does – you can add elements to the queue one after the other, then poll the queue to remove elements from the queue’s head.

The difference with a priority queue is that the elements in the queue are rearranged to conform to a given comparator, rather than using a simple FIFO ordering; as a result, when elements are removed from the queue, they are received in pre-sorted order. By default, elements are sorted based on their natural ordering and placed in ascending order.

In this example, after calling poll, the element 2 is removed from the priority queue, even through it was the most recent value placed. The reason for this is that 2 is the smallest value within the priority queue.

Regarding the inner workings of the priority queue, Java represents them as priority/min-heaps, which in turn are backed by fixed-size arrays. Here, we have a priority queue with 5 elements within an array format. Now, these 5 elements can also be shown in a tree structure as follows.

Next, we will sort this tree structure such that each child of a node in the tree, in this case 10 and 15, will be guaranteed to be smaller than the parent, in this case 25, if we sort the priority queue based on natural ordering.

With this representation, the priority queue can easily give us the maximum value within the queue as the maximum value is always going to be the topmost parent. Thus, priority queues give us automatic ordering without explicit sorting.

Follow along in the next video where we show you how you can create your own priority queue in Java.