Suppose you have M number of List/Array/Sequence and each one is sorted with total of N number of elements. So best optimal way to solve it with the the complexity O(NlogM) time using a heap.
Minimum of each sequence can form a heap with the O(logM) time to insert elements in the heap and O(1) time to delete an element.
Each element would take O(logM) time to insert in the heap and with the total number of elements N, it gives an O(NlogM) time solution.
In Java 1.5 onwards PriorityQueue/PriorityBlockingQueue are being introduced to cater as priority heap.
We are really thankful to Joshua Bloch, father of Java Collection Framework, to enlighten with the real world of programming in Java.
Following are the description available in the Oracle Docs Java 1.5 :
An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a
Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations
poll,remove, peek, and element access the element at the head of the queue.
A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.
This class and its iterator implement all of the optional methods of the
Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
Note that this implementation is not synchronized. Multiple threads should not access a
PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe PriorityBlockingQueueclass.
Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (
offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).
This class is a member of the Java Collections Framework.
/**
* @author sachin srivastava
* tek9g.blogspot.com
*
*/
public class MergingSortedSequence {
public static void main(String[] args) {
int[] arr1 = {1,3,6,4,8,90,133};
int[] arr2 = {2,3,1,17,18};
int[] arr3 = {4,5,6,8,11};
int[] arr4 = {125,9,10,13,34};
int[] arr = new int[arr1.length + arr2.length + arr3.length + arr4.length];
PriorityQueue<Integer> prq = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
if(i<arr1.length){
prq.add(arr1[i]);
}
if(i<arr2.length){
prq.add(arr2[i]);
}
if(i<arr3.length){
prq.add(arr3[i]);
}
if(i<arr4.length){
prq.add(arr4[i]);
}
}
while (!prq.isEmpty()) {
System.out.print(prq.poll()+" ");
}
}
}Output : 1 1 2 3 3 4 4 5 6 6 8 8 9 10 11 13 17 18 34 90 125 133
Output is sorted in the ascending order using Min heap .
Point here is if we don't have the M sorted sequence even then using the PriorityQueue , we can have a sorted collection .
Let see the example using the Random number generation :
public static void main(String[] args) {
/**
* @author sachin srivastava
* tek9g.blogspot.com
*
*/
PriorityQueue<Integer> prq = new PriorityQueue<>();
Random random = new Random();
for (int i = 0; i < 20; i++) {
int rand = random.nextInt(20);
System.out.print(rand +" ");
prq.add(rand);
}
System.out.println("\n------\n");
while (!prq.isEmpty()) {
System.out.print(prq.poll()+" ");
}
}
Output :
Random generated sequence :
8 11 18 14 6 5 10 19 7 3 3 17 14 10 18 8 17 5 5 9
------
Sorted merged sequence :
3 3 5 5 5 6 7 8 8 9 10 10 11 14 14 17 17 18 18 19
If you are working in a multithreaded environment then these thread should not have concurrent access to the PriorityQueue and if any of the thread is modifying the queue then to make it thread safe , we need to use PriorityBlockingQueue instead of PriorityQueue which has been designed to cater the concurrent modification problem.
In the above mentioned scenarios Min heap PriorityQueue is implemented which is by default the implementation of the queue.
If we want to create Max heap using the PriorityQueue then we need to pass the comparator to it and then output will be in the descending order.
Consider the above random number problem :
public static void main(String[] args) {
/**
* @author sachin srivastava
* tek9g.blogspot.com
*
*/
//Max heap by passing a comparator
PriorityQueue<Integer> prq = new PriorityQueue<>((x,y)-> y-x);
Random random = new Random();
for (int i = 0; i < 20; i++) {
int rand = random.nextInt(20);
System.out.print(rand +" ");
prq.add(rand);
}
System.out.println("\n------\n");
while (!prq.isEmpty()) {
System.out.print(prq.poll()+" ");
}
}
Output :
Random generated sequence :
17 0 4 12 9 11 5 12 12 12 3 18 19 9 9 17 8 19 1 14
------
Sorted merged sequence using the max heap in the descending order :
19 19 18 17 17 14 12 12 12 12 11 9 9 9 8 5 4 3 1 0
Enjoy the beautiful world of Java and coding !!!!!!
