Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Kotlin

Second Edition · Android 11 · Kotlin 1.5 · IntelliJ IDEA Community Edition 2021.1

Before You Begin

Section 0: 7 chapters
Show chapters Hide chapters

Section I: Introduction to Data Structures & Algorithms

Section 1: 2 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 8 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 6 chapters
Show chapters Hide chapters

13. Priority Queues
Written by Irina Galata

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Queues are lists that maintain the order of elements using first in, first out (FIFO) ordering. A priority queue is another version of a queue. However, instead of using FIFO ordering, elements are dequeued in priority order.

A priority queue can have either a:

  • Max-priority: The element at the front is always the largest.
  • Min-priority: The element at the front is always the smallest.

A priority queue is especially useful when you need to identify the maximum or minimum value within a list of elements.

In this chapter, you’ll learn the benefits of a priority queue and build one by leveraging the existing queue and heap data structures that you studied in previous chapters.

Applications

Some useful applications of a priority queue include:

  • Dijkstra’s algorithm: Uses a priority queue to calculate the minimum cost.
  • A* pathfinding algorithm: Uses a priority queue to track the unexplored routes that will produce the path with the shortest length.
  • Heap sort: Many heap sorts use a priority queue.
  • Huffman coding: Useful for building a compression tree. A min-priority queue is used to repeatedly find two nodes with the smallest frequency that don’t yet have a parent node.

Priority queues have many more applications and practical uses; the list above represents only a handful.

Common operations

In Chapter 5, “Queues”, you established the following interface for queues:

Implementation

You can create a priority queue in the following ways:

Using Comparable objects

AbstractPriorityQueue<T> implements the Queue<T> interface delegating to a Heap<T>. You can implement this using either Comparable<T> objects or a Comparator<T>. In this example, you’ll use the former.

Using Comparator objects

Providing different Comparator<T> interface implementations allows you to choose the priority criteria.

Challenges

Challenge 1: Constructing ArrayList priority queues

You learned to use a heap to construct a priority queue by implementing the Queue interface. Now, construct a priority queue using an ArrayList:

Solution 1

Recall that a priority queue dequeues elements in priority order. It could either be a min or max priority queue. To make an array-based priority queue, you need to implement the Queue interface. Instead of using a heap, you can use an array list.

Challenge 2: Sorting

Your favorite concert was sold out. Fortunately, there’s a waitlist for people who still want to go. However, the ticket sales will first prioritize someone with a military background, followed by seniority.

Solution 2

Given a list of people on the waitlist, you would like to prioritize the people in the following order:

Key points

  • A priority queue is often used to find the element in priority order.
  • The AbstractPriorityQueue<T> implementation creates a layer of abstraction by focusing on key operations of a queue and leaving out additional functionality provided by the heap data structure.
  • This makes the priority queue’s intent clear and concise. Its only job is to enqueue and dequeue elements, nothing else.
  • The AbstractPriorityQueue<T> implementation is another good example of Composition over (implementation) inheritance.
12. The Heap Data Structure
14. O(n²) Sorting Algorithms
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2026 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now