This repository has been archived by the owner on Mar 30, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
PriorityQueue.java
73 lines (64 loc) · 1.71 KB
/
PriorityQueue.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package assign10;
import java.util.NoSuchElementException;
/**
* This interface represents the priority queue abstract data type,
* defining the operations and running times expected of any data
* structure used to implement a priority queue.
*
* NOTE: The item with the highest priority is the "maximum" item.
*
* @author Erin Parker
* @version April 7, 2021
*
* @param <E>
*/
public interface PriorityQueue<E> {
/**
* Adds the given item to this priority queue.
* O(1) in the average case, O(log N) in the worst case
*
* @param item
*/
public void add(E item);
/**
* Returns, but does not remove, the maximum item this priority queue.
* O(1)
*
* @return the maximum item
* @throws NoSuchElementException if this priority queue is empty
*/
public E peek() throws NoSuchElementException;
/**
* Returns and removes the maximum item this priority queue.
* O(log N)
*
* @return the maximum item
* @throws NoSuchElementException if this priority queue is empty
*/
public E extractMax() throws NoSuchElementException;
/**
* Returns the number of items in this priority queue.
* O(1)
*/
public int size();
/**
* Returns true if this priority queue is empty, false otherwise.
* O(1)
*/
public boolean isEmpty();
/**
* Empties this priority queue of items.
* O(1)
*/
public void clear();
/**
* Creates and returns an array of the items in this priority queue,
* in the same order they appear in the backing array.
* O(N)
*
* (NOTE: This method is needed for grading purposes. The root item
* must be stored at index 0 in the returned array, regardless of
* whether it is in stored there in the backing array.)
*/
public Object[] toArray();
}