Priority Queue

Introduction

Prerequisites: Queue, Heap

A priority queue is a queue that takes elements which have the highest priority first. This is either the maximum or minimum property for all elements.

Consider a waiting list for lung transplants. The patients are given a score when they are placed on the waiting list based on whether they smoke, risk factors, age, expected time left, etc. When a lung is available, the patient with the highest score will receive the lung first. During this time, it is possible more patients could be added to the queue. The behaviour is similar to a queue but instead of the first person getting in the queue getting a lung first, the person with the highest score will get it. This means that if Sam, who has a score of 60, joins the queue after Bob, who has a score of 40, Sam will get the lung first even though Bob was in the queue before him.

A priority queue is an abstract data structure with two operations: push and pop. Push adds an element into the priority queue and pop removes the highest or lowest element.

A priority queue is usually implemented as a heap because it is the most efficient implementation.

Implementations

Exercises

1. Given a list of N numbers, find the M largest numbers. (Note you can do better than O(N log N)).
2. Given N lists of N numbers, find the N largest numbers.