The JDK 10.0.2
Some time ago on the Internet to brush the problem, encountered a problem to find the median, see a user to use PriorityQueue to achieve, feel its solution idea is quite good. Plus I had never used PriorityQueue before, so I tried to read the source code for that class and solved the problem with the same idea. Now to summarize the class, note that the article is algorithmic and data structure-centric and doesn’t consider other details. If you want to see that question, you can go directly to the quiz.
directory
Queue [], size, comparator Initialize (heapify) : Heapify (), siftDownComparable(k, e) three. Add elements: Offer (e), siftUpUsingComparator(k, e) iv. Index: indexOf(o) 5 Remove elements: remove(o), removeAt(I), removeEq(o) 6. Take top of heap: peek() seven. Delete heap top: poll() eight. Clear the queue: clear() nine. Iterating: iterator(), toArray(), toArray(T[] a) ten. Quiz: Median one in the data stream. The data structure
I have listed only the important attributes needed for the presentation, leaving out other details. The PriorityQueue is implemented internally in a heap. I’ll replace queue[] with pq[] for convenience.
PriorityQueue {/* Balanced binary heap for storing elements * n: 0 -> size-1 * pq[n].left = pq[2n+1] * pq[n].right = pq[2(n+1)] */ Object[] queue; int size; // the number of elements in pq. super E> comparator; // Custom comparator} copy code back to directory
Ii. Initialization (heapification)
If an existing collection is used to construct a PriorityQueue, heapify() is used to initialize pq[] (i.e., binary heapification) so that it satisfies heap properties. Heapify () in turn completes heapification by calling siftDownComparable(k, e). The source code is as follows:
View Code calls siftDownUsingComparator(k, e) if it has a custom comparator, or siftDownComparable(k, e) otherwise. These two methods compare the size of two elements in different forms, but otherwise the same, so we only need to look at one of the cases. For descriptive purposes, in the following example I use Integer as the storage element type for pq[], so siftDownComparable(k, e) is called. (size >>> 1 indicates size unsigned right 1 bit, equivalent to size / 2)
I’m not going to go through the source code, line by line, but try to use simple examples to show, I think through the example and later you read the source code, it will be easier to understand the content of the algorithm.
Now let’s look at the process of constructing a PriorityQueue using the set {2, 9, 8, 4, 7, 1, 3, 6, 5}. The algorithm time complexity is O(n), n = size. (Time complexity proof: Introduction to Algorithms (3rd edition) Chapter 6 6.3 Building heap)
I = (size >>> 1) -1, where size = 9, I = 3; By comparing the elements in Pq [3, 7, 8], the smallest element Pq [x] is interchanged with the top element pq[3]. Since Pq [x] = Pq [3], there is no interchange. Move to the next parent node I = 2. Similarly, compare the elements in Pq [2, 5, 6] and swap the smallest element Pq [5] with pq[2]. The following operations are the same. It should be noted that when PQ [1] (9) and PQ [3] (4) are exchanged (as shown in FIG. 2.d), PQ [3, 7, 8] violates the nature of the minimum heap, so further adjustment (downward adjustment) is required, and the adjustment ends when it reaches the leaf node (I >= size/2). Return to the directory
Three. Add elements
Add elements: add(e), offer(e), since adding elements can break the nature of the heap, you need to call siftUp(I, e) to adjust up to maintain the nature of the heap. Similarly, siftUp(I, e) calls a siftUpUsingComparator(k, e) or a siftUpComparable(k, e) depending on the presence or absence of a custom comparator. In my example, siftUpComparable(K, E) is used. Here is the source code for adding elements:
View Code source Code grow(I + 1) is used when pQ [] capacity is insufficient. Now look at adding element 1 to the minimum heap pq = {3, 5, 6, 7, 8, 9}. The time complexity of the algorithm is O(LGN), n = size.
SiftUp (k, e); siftUp(k, e); Parent = (k – 1) >>> 1; in this example, k = 6, parent = 2; Compare pQ [k] and PQ [parent], place the smaller one up and the larger one down, in this example, swap the positions of PQ [6] (1) and PQ [2] (6); After this swap, let k = parent and continue in the same way until k <= 0 (reaching the root). Return to the directory
Index of four.
IndexOf (O) is a private method, but it is called in many public methods, such as remove(O), contains(O), etc., so it is briefly mentioned here. The algorithm is not complicated. The time complexity is O(n), where n = size.
In the View Code indexOf(o), equals() is used to determine whether two elements are equal. In removeEq(o), equals() is used to determine whether two elements are equal.
Return to the directory
Delete elements
Remove (o) and removeEq(o) only use different methods to determine whether two elements are equal (equals() and removeEq(o) use ==). Otherwise, they both call removeAt(I) to perform the deletion. Deleting an element is likely to break the nature of the heap, so maintenance is also required. The maintenance of removing elements is slightly more complex than the maintenance of adding elements, because it may involve both up-tuning siftUp and down-tuning siftDown. The source code is as follows:
Pq = {0, 1, 7, 2, 3, 8, 9, 4, 5, 6} to understand how the algorithm works. Time complexity O(LGN), n = size.
Step 1: remove(6), indexOf(6) = 9, removeAt(9) (represented by r(9), the following is the same), since I = 9 is the end of the queue, the heap nature will not be damaged after deletion, so it can be directly deleted; The second step is remove(1), namely R (1). According to Figure (5.b), the algorithm replaces PQ [1] with queue tail PQ [8], which destroys the nature of the minimum heap and requires downward adjustment for maintenance. In the third step, remove(8), namely R (5), replaces Pq [5] with queue tail element Pq [7], which destroys the nature of the minimum heap and requires upward adjustment for maintenance. Return to the directory
Six. Take the top of the heap
Peek () can fetch the top element pq[0] in O(1) time complexity. See source code at a glance:
View Code goes back to the directory
Delete the heap top
Removing the top of the heap uses the poll() method, which is equivalent to removeAt(0) (time complexity O(LGN)), with the slight difference that it only involves downward adjustment, not upward adjustment. Friends who are not clear can refer to (five. Delete element), here is the source:
View Code goes back to the directory
Clear the queue
Clear queue clear(), which sets pq[I] to null and size to 0, but pq.length does not change. The time complexity is O(n), where n = size. The source code is as follows:
View Code goes back to the directory
9. Traversal
The pq[] itself can be iterated using an Iterator, or the toArray() and toArray(T[] a) methods can be called to generate a copy of the pq[]. The time complexity of traversal itself is O(n), n = size.
Use an iterator to traverse pq = {0, 1, 7, 2, 3, 8, 9, 4, 5, 6} as follows:
View Code is traversed by copying the pq[] copy as follows:
ToArray (T[] a); toArray(T[] a);
If ins[] has a capacity greater than x.size(), use for (int I = 0; i < x.size(); I++), otherwise you might get extra data; Or if you use for (int a: ins), NullPointerException may result; Please use ins = x.toarray (ins) to ensure that the correct copy of pQ [] is obtained. When the capacity of ins[] is larger than x.size(), the copy can be obtained correctly. When the capacity of ins[] is smaller than x.size(), the copy cannot be obtained correctly. In this case, toArray(T[] a) internally generates an Integer array of size x.size() to copy, and then returns the array. ToArray (T[] a) toArray(T[] a)
View Code goes back to the directory
10. Quiz
Here’s the topic I mentioned at the beginning of this article, as follows (click here to do it online) (use PriorityQueue to do it) :
How to obtain a median in a data stream? If an odd number of values are read from the data stream, the median is the number in the middle of all values sorted. If an even number of values are read from the data stream, the median is the average of the middle two numbers sorted by all the values. We use the Insert() method to read the data stream and the GetMedian() method to get the median of the data currently read. * /
Public class Solution {public void Insert(Integer num) {} public Double GetMedian() {}
View Code welcomes Java engineers who have worked for one to five years to join the Java community: 891219277 Group provides free Java architecture learning materials (which have high availability, high concurrency, high performance and distributed, Jvm performance tuning, Spring source code, MyBatis, Netty, Redis, Kafka, Mysql, Zookeeper, Tomcat, Docker, Dubbo, multiple knowledge architecture data, such as the Nginx) reasonable use their every minute and second time to learn to improve yourself, don’t use “no time” to hide his ideas on the lazy! While young, hard to fight, to the future of their own account!