import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

public class priorityQueueUse {

    public static void main(String args[]) {

        priorityQueueUse pqUse = new priorityQueueUse();
        int[] arr = pqUse.sortKSorted(new int[] { 2, 1, 4, 8, 6, 9 }, 2);
        System.out.println(Arrays.toString(arr));
        pqUse.checkMaxHeap(new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 7 });
        System.out.println(pqUse.kthLargest(new int[] { 10101, 565, 4921, 60 }, 2));
        pqUse.findMedian(new int[] { 6, 2, 1, 3, 7, 5 });

        System.out.println();
    }

    /*
     * Given a K sorted array- It is expected that the sorted array is returned.
     * K sorted array: The final position of every element is within
     * k elements of the current position. For example: [2,1,4,8,6,9] and k = 2.
     * Every element's final position is within 2 elements (+2 and -2) to the
     * current position.
     * 
     * Solution: Create a heap of size k, add first k elements, remove one by one
     * and put it in the array from the starting. This will be done for arr.length -
     * k
     * times. There will come a time when the last k elements are still available.
     * At that time, they will be present in the heap, just remove and put them.
     */

    public int[] sortKSorted(int arr[], int k) {

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for (int i = 0; i < k; i++) {
            pq.add(arr[i]);
        }
        int i = 0;
        while (i < arr.length - k) {
            int value = pq.remove();
            pq.add(arr[i + k]);
            arr[i] = value;
            i++;
        }

        for (int j = arr.length - k; j < arr.length; j++) {
            arr[j] = pq.remove();
        }
        return arr;
        // The array should be sorted.
    }

    // Return K Largest elements of the array.
    public ArrayList<Integer> kLargest(int[] input, int k) {

        /*
         * Another way to create max Priority Queue.
         * PriorityQueue<Integer> pq = new
         * PriorityQueue<Integer>(Collections.reverseOrder());
         */

        maxPriorityQueue maxPQ = new maxPriorityQueue();
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(maxPQ);
        ArrayList<Integer> alist = new ArrayList<Integer>();
        for (Integer a : input) {
            pq.add(a);
        }
        for (int i = 0; i < k; i++) {
            alist.add(pq.remove());
        }

        return alist;
    }

    /*
     * A better solution will be that instead of adding all
     * the elements to the PriorityQueue which takes O(n), we add
     * only the first k elements to the pq. Then, for the remaining
     * elements, we just have to check if the smallest of the pq is
     * larger than the remianing elements. This will take only O(k)
     */

    public ArrayList<Integer> kLargest2(int[] input, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for (int i = 0; i < k; i++) {
            pq.add(input[i]);
        }
        for (int i = k; i < input.length; i++) {
            if (pq.peek() < input[i]) {
                pq.remove();
                pq.add(input[i]);
            }
        }
        return new ArrayList<Integer>(pq);
    }

    public ArrayList<Integer> kSmallest(int[] input, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        ArrayList<Integer> alist = new ArrayList<Integer>();
        for (Integer a : input) {
            pq.add(a);
        }
        for (int i = 0; i < k; i++) {
            alist.add(pq.remove());
        }

        return alist;
    }

    public class minPriorityQueue implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o1 > o2)
                return 1;
            if (o1 < o2)
                return -1;
            return 0;
        }
    }

    public class maxPriorityQueue implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o1 < o2)
                return 1;
            if (o1 > o2)
                return -1;
            return 0;
        }
    }

    public boolean checkMaxHeap(int arr[]) {
        int parent = 0;
        int leftChild, rightChild;
        while ((2 * parent + 1) < arr.length) {
            leftChild = 2 * parent + 1;
            rightChild = 2 * parent + 2;
            if (arr[leftChild] > arr[parent]) {
                return false;
            }
            if (arr.length - 1 >= rightChild && arr[rightChild] > arr[parent]) {
                return false;
            }
            parent++;
        }
        return true;
    }

    // return the Kth Largest element.
    public int kthLargest(int[] input, int k) {

        /*
         * Create a min heap of size arr.length - K, such that
         * the top most element will be the Kth largest element.
         * Then for the remaining elemenst check if the peek of
         * the queue is larger or not - If yes then we are good.
         * If no, then replace.
         */

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for (int i = 0; i < k; i++) {
            pq.add(input[i]);
        }

        for (int i = k; i < input.length; i++) {
            if (pq.peek() < input[i]) {
                pq.remove();
                pq.add(input[i]);
            }
        }

        return pq.peek();
    }

    /*
     * Given k different sorted arrays of different sizes,
     * we need to merge the given arrays such that result
     * should be sorted as well.
     */
    public ArrayList<Integer> mergeKSortedArrays(ArrayList<ArrayList<Integer>> input) {

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        ArrayList<Integer> alist = new ArrayList<Integer>();

        for (ArrayList<Integer> list : input) {
            for (Integer value : list) {
                pq.add(value);
            }
        }

        while (!pq.isEmpty()) {
            alist.add(pq.remove());
        }

        return alist;
    }

    // We have to print the running Median. For every i-th integer added to the
    // running list of integers, print the resulting median.

    public void findMedian(int arr[]) {

        /*
         * Approach: Keep two heaps, one max heap and one min heap.
         * The larger elements will be placed in the min heap while the smaller
         * elements will be placed in the max heap. Such that at any point, the
         * max heap will return the largest of the smaller elements, while the min
         * heap will return the smallest of the larger elements. The largest element
         * in the max heap will be smaller than the smallest element in the min heap.
         * The average of removal of both the heaps will be the median, if there
         * are even number of elements. If there are odd number of elements, then
         * the removal will happen from the larger of the two heaps, which will
         * be the median.
         * 
         * This whole idea works only when elements are added in the correct order.
         * Always maintain: abs(maxHeap.size - minHeap.size) <= 1
         * 
         * Add first element to max heap.
         * If maxHeap.peek() > new element -> Add new element to max heap, and existing
         * to min heap.
         * If maxHeap.peek() < new element -> Add new element into min heap.
         * 
         * Now, we have following three items:
         * minHeap.peek(), maxHeap.peek() and new element.
         * Remember: minHeap.peek() > maxHeap.peek(), This should be maintained always.
         * 
         * new-element > minHeap.peek(),
         * If size of min Heap is greater, remove one from minHeap, add to the maxheap
         * and add the new element to the min Heap. Otherwise just add to the min heap.
         * 
         * new-element < maxHeap.peek(),
         * If size of max Heap is greater, remove one from maxHeap, add to the minheap
         * and add the new element to the max Heap. Otherwise just add to the max heap.
         * 
         * maxHeap.peek() < new-element < minHeap.peek()
         * Just add the element into the smaller heap. If sizes are same, add to the one
         * where difference between the peek and the new element is smaller.
         * 
         * At any point, when we have to print the median, we will not actually remove
         * the element, but just have a look at the peek(), since who will do the task
         * of
         * adding the elements back into the respective heaps.
         */

        if (arr.length == 0) {
            System.out.println(arr.length);
            return;
        } else if (arr.length == 1) {
            System.out.println(arr[0]);
            return;
        }

        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

        int minHeap_size = 0;
        int maxHeap_size = 0;

        // Add the first element to the max heap.
        maxHeap.add(arr[0]);
        System.out.println(maxHeap.peek());

        for (int i = 1; i < arr.length; i++) {

            minHeap_size = minHeap.size();
            maxHeap_size = maxHeap.size();

            if (maxHeap_size > minHeap_size) {

                if (maxHeap.peek() > arr[i]) {
                    minHeap.add(maxHeap.remove());
                    maxHeap.add(arr[i]);
                } else if (minHeap.peek() < arr[i]) {
                    minHeap.add(arr[i]);
                } else {
                    minHeap.add(arr[i]);
                }

            } else if (maxHeap_size < minHeap_size) {

                if (maxHeap.peek() > arr[i]) {
                    maxHeap.add(arr[i]);
                } else if (minHeap.peek() < arr[i]) {
                    maxHeap.add(minHeap.remove());
                    minHeap.add(arr[i]);
                } else {
                    maxHeap.add(arr[i]);
                }

            } else {
                if (Math.abs(maxHeap.peek() - arr[i]) > Math.abs(minHeap.peek() - arr[i])) {
                    minHeap.add(arr[i]);
                } else if (Math.abs(maxHeap.peek() - arr[i]) < Math.abs(minHeap.peek() - arr[i])) {
                    maxHeap.add(arr[i]);
                } else {
                    maxHeap.add(arr[i]);
                }
            }

            minHeap_size = minHeap.size();
            maxHeap_size = maxHeap.size();

            if (minHeap_size > maxHeap_size) {
                System.out.println(minHeap.peek());
            } else if (minHeap_size < maxHeap_size) {
                System.out.println(maxHeap.peek());
            } else {
                System.out.println((maxHeap.peek() + minHeap.peek()) / 2);
            }
        }
    }

    public int[] frequentElements(int[] arr, int k) {

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int element : arr) {
            map.put(element, map.getOrDefault(element, 0) + 1);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> map.get(b) - map.get(a));

        pq.addAll(map.keySet());
        int[] output = new int[k];
        int i = 0;
        while (i < k) {
            output[i] = pq.poll();
            i++;
        }
        return output;

    }

    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {

        PriorityQueue<Integer> difference = new PriorityQueue<Integer>((a, b) -> b - a);

        for (int i = 0; i < nums1.length; i++) {
            difference.add(Math.abs(nums1[i] - nums2[i]));
        }

        while (k1 != 0) {
            if (difference.peek() == 0)
                break;
            int value = difference.poll() - 1;
            difference.add(value);
            k1--;
        }

        while (k2 != 0) {
            if (difference.peek() == 0)
                break;
            int value = difference.poll() - 1;
            difference.add(value);
            k2--;
        }

        Long sum = 0L;
        while (!difference.isEmpty()) {
            int value = difference.poll();
            sum = Math.multiplyFull(value, value) + sum;
        }

        return sum;
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        
        ArrayList<int[]> alist = new ArrayList<int[]>();
        
        for(int i = 0; i< nums1.length; i++){
            for(int j = 0; j< nums2.length; j++){
                int[] arr = {nums1[i] , nums2[j]};
                alist.add(arr);
            }
        }
        
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((arr1, arr2) -> {
            int sum1 = Arrays.stream(arr1).sum();
            int sum2 = Arrays.stream(arr2).sum();
            return Integer.compare(sum1, sum2);
        });
        
        pq.addAll(alist);
        
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        while(k != 0){
            int[] arr = pq.remove();
            list.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
            k--;
        }
        
        return list;
    }
}