OK, the smallest element is always on the left. Priority Queue Using a Min-Heap – The Algorithm The min-heap of the PriorityQueue created in the example is precisely the one I displayed at the beginning of the article. And if you look closely, you'll see that the numbers are in the same order as in the graphical array representation above. The output of the program is: priorityQueue = Code language: plaintext ( plaintext ) ( "priorityQueue = " + priorityQueue) Code language: Java ( java ) The following lines of code demonstrate this well: PriorityQueue priorityQueue = new PriorityQueue() What you see is the array representation of the min-heap underlying the PriorityQueue. This is why, when you print a Java PriorityQueue as a string, you see the smallest element on the left. We can achieve this by using the static method (): PriorityQueue reversedQueue = new PriorityQueue(Collections.reverseOrder()) ĪssertThat(reversedQueue.poll()).isEqualTo(3) ĪssertThat(reversedQueue.poll()).isEqualTo(2) ĪssertThat(reversedQueue.poll()).isEqualTo(1) 4.In a min-heap, the smallest element is always at the top, i.e., in the array, it is always at the first position. Let’s now create a PriorityQueue sorted in the inverse natural order. isEqualTo(integerQueueWithComparator.poll()) PriorityQueue integerQueueWithComparator = new PriorityQueue((Integer c1, Integer c2) -> pare(c1, c2)) That’s because initializing a priority queue with a null Comparator will directly order elements using the compare operation.Īs an example, let’s now see that by providing a standard Integer natural ordering comparator or null, the queue will be ordered in the same way: PriorityQueue integerQueue = new PriorityQueue() In a previous article, we presented how elements inserted into the PriorityQueue are ordered based on their natural ordering. It is instead granted linear time for the remove(Object) and contains(Object) methods and constant time for the retrieval methods ( peek, element, and size). This can happen thanks to the Balanced Binary Heap data structure that is constantly maintained for every edit to the Queue. In the Javadoc, it’s specified that this implementation takes O(log(n)) time for the enqueuing and dequeuing methods ( offer, poll, remove and add). While it’s not mandatory to give an initial capacity to a PriorityQueue, if we already know the size of our collection, it’s possible to avoid automatic resizes, which consume CPU cycles that we’d be better off saving. This array is automatically resized if the initial specified capacity (11 by default in JDK 17) is not enough to store all the items. Internally, the PriorityQueue relies on an array of objects. Every retrieval operation of the queue ( poll, remove, or peek) reads the head of the queue. As we may infer from its name, we use PriorityQueue to maintain a defined ordering in a given collection: the first element ( head) of the queue is the most minor element with respect to the ordering we specify. The class was provided starting from the JDK 1.5, which also contains other implementations of the AbstractQueue.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |