priority queue ADT

Complete

Summary

Priority queue ADT

each element has a priority

Circular array implementation - compact array

keep the array sorted by priority

Operation	Method	Performance
`enqueue(v)`	Expensive enqueue: insert into sorted array, one round of insertion sort Append: add at back	- -
`dequeue()`	Pop: remove from front Expensive dequeue: search for highest priority, one round of selection sort	- -

to sort the array first for expensive enqueue approach, linear DS is not good

Priority queue class

java.util.PriorityQueue - binary min heap

Library implementation

java

PriorityQueue<Integer> pq = new PriorityQueue<>(); // min heap by default
// or
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // to make a max heap

// enqueue(v)
pq.offer(1);
pq.offer(0);

Concept

Priority queue operations

enqueue(v)
- add v to the queue
dequeue()
- get the item in the queue with the highest priority and remove it

similar to queue operations, just that dequeuing is done by order of priority instead of order of entry