Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Explore the English language on a new scale using AI-powered English language navigator.

Priority queue ADT

In practice we often deal with priorities. For instance, in a to-do-list for a day, each task has an associated significance. Is absolutely necessary to collect a car from repair shop (highest priority) and you may possibly watch a new film (lowest priority). Besides real life examples, many computer tasks work with priorities. Frequently cited instance is the Dijkstra's shortest path algorithm. Priority queue ADT lets us to work with objects that have an associated priority.

In the application we have a pair (priority, item) where an item is some auxiliary data priority is associated with. To maintain simplicity, we omit priorities and consider that for items e1, e2: e1 < e2 means e1 has higher priority than e2.

Operations

  • PriorityQueue create()
    creates empty priority queue

  • boolean isEmpty(PriorityQueue pq)
    tells whether priority queue pq is empty

  • insert(PriorityQueue pq, Item e)
    inserts item e to priority queue pq

  • Item minimum(PriorityQueue pq)
    tells minimal item in priority queue pq
    Precondition: pq is not empty

  • removeMin(PriorityQueue pq)
    removes minimum item from priority queue pq
    Precondition: pq is not empty

  • destroy(PriorityQueue pq)
    destroys priority queue pq

Implementations

Recommended books

  1. Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
  2. Robert Lafore. Data Structures and Algorithms in Java. (Practice)
  3. Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)

Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.


Every dollar helps!

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: