priority queue
Summary
Priority queue
- each element has a priority
Circular array implementation - compact array
- keep the array sorted by priority
| Operation | Method | Performance |
|---|---|---|
insert(v) | Expensive insert: insert into sorted array, one round of insertion sort Append: add at back | - - |
extract() | Pop: remove from front Expensive extract: search for highest priority, one round of selection sort | - - |
to sort the array first for expensive enqueue approach, linear DS is not good
Concept
Priority queue operations
insert(v)- add
vto the queue
- add
extract()- 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