§ 2.4 Priority Queues.
Lecture
Namespace:SedgewickWayne.Algorithms
Folder: PriorityQueues
| Name | Princeton java link | Misc |
|---|---|---|
| IndexMaxPQ | IndexMaxPQ.java | IndexMaxPQ.cs |
| IndexMinPQ | IndexMinPQ.java | IndexMinPQ.cs |
| MaxPQ | MaxPQ.java | MaxPQ.cs |
| MinPQ | MinPQ.java | MinPQ.cs |
| UnorderedArrayMaxPQ | UnorderedArrayMaxPQ.java | UnorderedArrayMaxPQ.cs |
| OrderedArrayMaxPQ | OrderedArrayMaxPQ.java | OrderedArrayMaxPQ.cs |
| X | FibonacciMinPQ.java | - |
| IndexFibonacciMinPQ | IndexFibonacciMinPQ.java | - |
| IPriorityQueue | IMaxPriorityQueue | IMinPriorityQueue | desc |
|---|---|---|---|
| Top | Max | Min | largest / lowest key |
| Delete | DeleteMax | DeleteMin | Removes top key and returns it |
| Index | MaxIndex | MinIndex | index associated with a minimum/maximum key |
| impl | insert | del max | max | remarks |
|---|---|---|---|---|
| unordered array | 1 | n | n | |
| ordered array | n | 1 | 1 | |
| binary heap | logn | logn | 1 | |
| d-ary heap | logdn |
dlogdn |
1 | sweet spot (d=4) |
| Fibonacci | 1 | log n`` | 1 | amortized log n |
| Brodal | 1 | log n | 1 | |
| holy grail | 1 | 1 | 1 | impossible |