Priority Queues/Sorted: Difference between revisions
From charlesreid1
(Created page with "Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/SortedPriorityQueue.java Sorted priority queue class implements a sorted list t...") |
No edit summary |
||
| Line 1: | Line 1: | ||
==Git Code== | |||
Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/SortedPriorityQueue.java | Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/SortedPriorityQueue.java | ||
==Notes== | |||
{{Main|Priority Queues}} | |||
Sorted priority queue class implements a sorted list to keep track of items in the priority queue. | Sorted priority queue class implements a sorted list to keep track of items in the priority queue. | ||
| Line 8: | Line 14: | ||
The removal of the minimum item is then very easy - it is removed from the front of the list. Removal (and peek) is an O(1) operation. | The removal of the minimum item is then very easy - it is removed from the front of the list. Removal (and peek) is an O(1) operation. | ||
==Flags== | |||
[[Category:Priority Queues]] | |||
[[Category:Queues]] | |||
{{StacksQueues}} | |||
Revision as of 03:40, 22 June 2017
Git Code
Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/SortedPriorityQueue.java
Notes
Main article: Priority Queues
Sorted priority queue class implements a sorted list to keep track of items in the priority queue.
This class implements insertion sort for each add operation to keep the minimum at the front of the list.
This means add() is O(N).
The removal of the minimum item is then very easy - it is removed from the front of the list. Removal (and peek) is an O(1) operation.