Priority Queues

Priority queues can be implemented using heaps. An ordinary queue is a first-in, first-out data structure. Elements are appended to the end of the queue and removed from the beginning. In a priority queue, elements are assigned with priorities. When accessing elements, the element with the highest priority is removed first. For example, the emergency room in a hospital assigns priority numbers to patients; the patient with the highest priority is treated first.

A priority queue can be implemented using a heap, in which the root is the object with the highest priority in the queue. Heaps were introduced in Heap Sort. The class diagram for the priority queue is shown in Figure below. Its implementation is given in the code below.

The code below gives an example of using a priority queue for patients. The Patient class is defined in lines 21–38. Four patients are created with associated priority values in lines 6–9. Line 8 creates a priority queue. The patients are enqueued in lines 12–15. Line 18 dequeues a patient from the queue.

Cindy(priority:7) Tim(priority:5) John(priority:2) Jim(priority:1)

The above is the detailed content of Priority Queues. For more information, please follow other related articles on the PHP Chinese website!