Package algs24
Class MinPQ<K extends Comparable<? super K>>
java.lang.Object
algs24.MinPQ<K>
- All Implemented Interfaces:
Iterable<K>
The
MinPQ
class represents a priority queue of generic keys.
It supports the usual insert and delete-the-minimum
operations, along with methods for peeking at the maximum key,
testing if the priority queue is empty, and iterating through
the keys.
The insert and delete-the-minimum operations take logarithmic amortized time. The min, size, and is-empty operations take constant time. Construction takes time proportional to the specified capacity or the number of items used to initialize the data structure.
This implementation uses a binary heap.
For additional documentation, see Section 2.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
-
Nested Class Summary
-
Field Summary
Modifier and TypeFieldDescriptionprivate Comparator
<? super K> static boolean
A test client.private int
private K[]
-
Constructor Summary
ConstructorDescriptionMinPQ()
Create an empty priority queue.MinPQ
(int initCapacity) Create an empty priority queue with the given initial capacity.MinPQ
(int initCapacity, Comparator<? super K> comparator) MinPQ
(Comparator<? super K> comparator) Create an empty priority queue using the given comparator.Create a priority queue with the given items. -
Method Summary
Modifier and TypeMethodDescriptiondelMin()
Delete and return the smallest key on the priority queue.private void
exch
(int i, int j) private boolean
greater
(int i, int j) void
Add a new key to the priority queue.boolean
isEmpty()
Is the priority queue empty?private boolean
private boolean
isMinHeap
(int k) iterator()
Return an iterator that iterates over all of the keys on the priority queue in ascending order.static void
min()
Return the smallest key on the priority queue.private void
resize
(int capacity) (package private) void
showHeap()
private void
sink
(int k) int
size()
Return the number of items on the priority queue.private void
swim
(int k) Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Field Details
-
pq
-
N
-
comparator
-
DEBUG
A test client.
-
-
Constructor Details
-
MinPQ
-
MinPQ
Create an empty priority queue with the given initial capacity. -
MinPQ
Create an empty priority queue using the given comparator. -
MinPQ
public MinPQ()Create an empty priority queue. -
MinPQ
Create a priority queue with the given items. Takes time proportional to the number of items using sink-based heap construction.
-
-
Method Details
-
resize
-
isEmpty
Is the priority queue empty? -
size
Return the number of items on the priority queue. -
min
Return the smallest key on the priority queue.- Throws:
NoSuchElementException
- if the priority queue is empty.
-
insert
Add a new key to the priority queue. -
delMin
Delete and return the smallest key on the priority queue.- Throws:
NoSuchElementException
- if the priority queue is empty.
-
swim
-
sink
-
greater
-
exch
-
isMinHeap
-
isMinHeap
-
iterator
Return an iterator that iterates over all of the keys on the priority queue in ascending order.The iterator doesn't implement
remove()
since it's optional.- Specified by:
iterator
in interfaceIterable<K extends Comparable<? super K>>
-
showHeap
void showHeap() -
main
-