Priority Queues/Unsorted: Difference between revisions
From charlesreid1
(Created page with "Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/UnsortedPriorityQueue.java The unsorted priority queue makes adding very fast -...") |
m (Replacing charlesreid1.com:3000 with git.charlesreid1.com) |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Link on git.charlesreid1.com: https://charlesreid1.com | ==Git Code== | ||
Link on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/priority-queues/UnsortedPQ.java | |||
==Implementation== | |||
Note: you can find a much more detailed walkthrough of a nearly identical class at [[Priority Queues/Sorted#Implementation]]. | |||
===Insert Method=== | |||
{{Main|Priority Queues}} | |||
The unsorted priority queue makes adding very fast - add operations are O(1), because items are just added to the end of the list, in no particular order. | The unsorted priority queue makes adding very fast - add operations are O(1), because items are just added to the end of the list, in no particular order. | ||
Removing the minimum item is an O(N) operation, since the entire array must be traversed to find the minimum element. Note that finding the minimum also requires examining every item in the list. | Removing the minimum item is an O(N) operation, since the entire array must be traversed to find the minimum element. Note that finding the minimum also requires examining every item in the list. | ||
==Flags== | |||
[[Category:Priority Queues]] | |||
[[Category:Queues]] | |||
{{StacksQueuesFlag}} | |||
Latest revision as of 03:45, 9 October 2019
Git Code
Link on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/priority-queues/UnsortedPQ.java
Implementation
Note: you can find a much more detailed walkthrough of a nearly identical class at Priority Queues/Sorted#Implementation.
Insert Method
The unsorted priority queue makes adding very fast - add operations are O(1), because items are just added to the end of the list, in no particular order.
Removing the minimum item is an O(N) operation, since the entire array must be traversed to find the minimum element. Note that finding the minimum also requires examining every item in the list.
Flags
 |
Stacks and Queues Part of Computer Science Notes
Series on Data Structures
Stacks and Queues: Python StacksQueues/Python · StacksQueues/Python/ArrayStack · StacksQueues/Python/ArrayQueue · StacksQueues/Python/ArrayDeque StacksQueues/Python/LinkedStack
Stacks and Queues: Java StacksQueues/Java · StacksQueues/Java/ArrayStack · StacksQueues/Java/ArrayQueue · StacksQueues/Java/ArrayQueueFS · StacksQueues/Java/ArrayDeque StacksQueues/Java/LinkedStack · StacksQueues/Java/LinkedQueue · StacksQueues/Java/LinkedDeque
Applications Postfix_Expressions#Stacks · StacksQueues/Subsets · StacksQueues/Subsets/Java
|