Facts about Priority Queues
Strict ordering of data using elements importance.
Can only access and process most important item.
Requires comparing elements to provide ordering.
///////////////////////////////////////////////////
Only access item at front
Only remove item at front
Wo
Can Null be a priority queue element?
No, rare to use null to compare
What is returned by its methods?
The most important element.
Smaller elements more Important than larger elements.
List Based Priority Queue
-Elements stored in smallest-to largest priority
.
Add method
#NAME?
Remove Method
Always uses index 0
Big Oh complexity
- add(); O(n) - shifting around, scans through list because of comparing
- remove(); O(1) - we know where it is, at index 0 most important gets removed first. Only if using linked list and size-1 for list.
- element(); O(1)
Where is the 2nd most important element at?
Doesn't matter only care about "Priority".
Priority Queue with Binary Tree
Binary Tree, Each level must be filled before starting next one.
Lowest level must be filled in from Left to Right.
Heap order Property
Nodes element more important "smaller than" than childrens'
Order Removed From a Priority Queue
Al", "Ch", "Ki", "Zu"
Smaller Elements are more important.
Most important in a Priority Queue for "Adding
1.) Most important at index 0
2.)Must compare new element with existing elements to see where it should be added.
Most important in a Priority Queue for "Removing
1.)Removes most important first at index 0.
Nodes element relative to Grandchild
Node's element is more important than grandchildren's elements.