Heaps.txt

SOLUTIONS OF THESE QUESTIONS ARE EITHER ON GFG OR ON LEETCODE.
---------------------------------------HEAPS-----------------------------------------
	

1. Construct Heap.
public class Heap {      //min heap
	ArrayList<Integer> data = new ArrayList<>();

	public int size() {
		return data.size();
	}
	
	public boolean isEmpty() {
		return size() == 0;
	}

	public void display() {
		System.out.println(data);
	}

	public int get() {
		return data.get(0);
	}

	public void add(int item) {
		data.add(item);
		upheapify(data.size() - 1);
	}

	private void upheapify(int ci) {

		int pi = (ci - 1) / 2;
		if (data.get(pi) > data.get(ci)) {
			swap(pi, ci);
			upheapify(pi);
		}
		
	}

	private void swap(int i, int j) {
		int ith = data.get(i);
		int jth = data.get(j);

		data.set(i, jth);
		data.set(j, ith);
	}

	public int remove() {
		swap(0, data.size() - 1);
		int temp = data.remove(data.size() - 1);
		downheapify(0);
		return temp;
	}

	private void downheapify(int pi) {
		int mini = pi;
		int lci = 2 * pi + 1;
		int rci = 2 * pi + 2;

		if (lci < data.size() && (data.get(mini) > data.get(lci))) { 
// checking with size saves from array index out of bound exception
												
			mini = lci;
		}
		if (rci < data.size() && (data.get(mini) > data.get(rci))) {
			mini = rci;
		}

		if (mini != pi) { // this saves from Stackoverflow
			swap(mini, pi);
			downheapify(mini);

		}
	}
}
-------------------------------------------------------------------------------------------------
2. Merge k Sorted Lists
 public ListNode mergeKLists(ListNode[] lists) {
    
        PriorityQueue<ListNode>pq=new PriorityQueue<>((a,b)->(a.val-b.val));
        
       for(ListNode l:lists){
           if(l!=null)
           pq.add(l);
       }
        
        ListNode dummy=new ListNode(0);
        ListNode prev=dummy;
        while(!pq.isEmpty()){
            ListNode rn=pq.remove();
            prev.next=rn;
             prev=prev.next;
            rn=rn.next;
            if(rn!=null){
                pq.add(rn);
            }
           
        }
        prev.next=null;
        return dummy.next;
    }
-------------------------------------------------------------------------------------------------
3. K Largest Elements
 int[] kLargest(int[] arr, int n, int k) {
       int[]krr=new int[k];
       PriorityQueue<Integer>pq=new PriorityQueue<>();
       
       for(int i=0;i<k;i++){
           pq.add(arr[i]);
       }
       
       for(int i=k;i<n;i++){
           if(pq.peek()<arr[i]){
               pq.remove();
               pq.add(arr[i]);
           }
       }
       int idx=krr.length-1;
       while(!pq.isEmpty()){
           krr[idx--]=pq.remove();
       }
       
       return krr;
    }
-> And for K largest/Smallest Element  donot store just get the first element of heap to get ANS.
-------------------------------------------------------------------------------------------------
4. Merge K sorted Arrays

	static class Pair {
		int data;
		int listno;
		int idx;
	}

	public static ArrayList<Integer> mergeKArrays(int[][] arr, int K) {
		PriorityQueue<Pair> hp = new PriorityQueue<>((a, b) -> a.data - b.data);
		ArrayList<Integer> ans = new ArrayList<Integer>();

		for (int i = 0; i < arr.length; i++) {
			Pair np = new Pair();
			np.data = arr[i][0];
			np.listno = i;
			np.idx = 0;
			hp.add(np);
		}

		while (!hp.isEmpty()) {
			Pair rp = hp.remove();
			ans.add(rp.data);
			rp.idx++;

			if (rp.idx < arr[rp.listno].length) {
				rp.data = arr[rp.listno][rp.idx];
				hp.add(rp);
			}
		}
		return ans;
	}
-------------------------------------------------------------------------------------------------
5. Reorganize String-Leetcode 767
public String reorganizeString(String S) {
        HashMap<Character,Integer>map=new HashMap<>();
        
        for(char ch:S.toCharArray()){
        map.put(ch,map.getOrDefault(ch,0)+1);    
        }
        
        //used lambda as comparator 
        PriorityQueue<Character>hp=new PriorityQueue<>((a,b)->map.get(b)-map.get(a));
        hp.addAll(map.keySet());
        
        StringBuilder sb= new StringBuilder();
        
        while(hp.size()>1){
            char first=hp.remove();
            char second=hp.remove();
            
            sb.append(first);
            sb.append(second);
            
            map.put(first,map.get(first)-1);
            map.put(second,map.get(second)-1);
            
            if(map.get(first)>0){
                hp.add(first);
            }
            if(map.get(second)>0){
                hp.add(second);
            }
        }
        
        if(hp.size()!=0){
            char last=hp.remove();
            if(map.get(last)>1){
                return "";
            }else{
                sb.append(last);
            }
        }
        return sb.toString();        
        
        }

-> Very Similar problem 
(Longest Happy String Leetcode-1405)

public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<pair> pq = new PriorityQueue<>((x,y)->(y.count - x.count));
        
        if(a>0)pq.add(new pair('a',a));
        if(b>0)pq.add(new pair('b',b));
        if(c>0)pq.add(new pair('c',c));

        StringBuilder ans = new StringBuilder();
        while(pq.size()>1){
            pair first = pq.poll();
            
            if(first.count>=2){
                ans.append(first.ch);
                ans.append(first.ch);
                first.count-=2;    
            }else{
                ans.append(first.ch);
                first.count-=1;
            }
                        
            pair second = pq.poll();
            
            if(second.count>=2 && first.count<second.count){
                ans.append(second.ch);
                ans.append(second.ch);
                second.count-=2;
            }else{
                ans.append(second.ch);
                second.count-=1;
            }
            
            if(first.count>0) pq.add(first);
            
            if(second.count>0) pq.add(second);

        }
        
        if(!pq.isEmpty()){
            pair rp = pq.poll();
            if(rp.count>=2){
                ans.append(rp.ch);
                ans.append(rp.ch);
                rp.count-=2;
            }else{
                ans.append(rp.ch);
                rp.count-=1;
            }
        }
        
        return ans.toString();
    }
-------------------------------------------------------------------------------------------------

***Important Point-> when we build heap from array we only have to deal with internal nodes, because for heapify left subtree and right subtree should be in heap, we don't care about leaf nodes as they are already follow the heap property. 
For Complete Binary Tree->n-1 levels completely filled, nth level: l->r
Internal Nodes->0 to (n/2)-1;
Leaf Nodes-> n/2 to n-1;
---------------------------------------------------
6. Heap Sort
 //Function to build a Heap from array.
    void buildHeap(int arr[], int n)
    {
        for(int i=n/2-1;i>=0;i--){
            heapify(arr,n,i);
        }
    }
 
    //Heapify function to maintain heap property.(max heap here)
    void heapify(int arr[], int n, int i)
    {
       int max=i;
       int lc=2*i+1;
       int rc=2*i+2;
       
       if(lc<n && arr[lc]>arr[max]){
           max=lc;
       }
       if(rc<n && arr[rc]>arr[max]){
           max=rc;
       }
       if(max!=i){ //to avoid stackoverflow
          int temp=arr[max];
            arr[max]=arr[i];
            arr[i]=temp;
            heapify(arr,n,max);   
       }
       
    }
    
    //Function to sort an array using Heap Sort.
    public void heapSort(int arr[], int n)
    {
	// here making max heap
        buildHeap(arr,n);
        for(int i=n-1;i>0;i--){
            //swapping with first element to get the desired order
            int temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
            heapify(arr,i,0);   //heapify for the reduced heap 
        }
    }
-------------------------------------------------------------------------------------------------
7. Maximum in all subarrays of size K    (Do this question with Queue only to improve time complexity)
public int[] maxSlidingWindow(int[] arr, int k) {
        PriorityQueue<pair>hp=new PriorityQueue<>();
       int[]res=new int[arr.length-k+1];
        int i=0;
        int j=0;
        
        while(j<arr.length){
            pair p=new pair(j,arr[j]);
            hp.add(p);
            if(j-i+1<k){
                j++;
            }else{
                res[i]=hp.peek().val;
                while(!hp.isEmpty() && hp.peek().key<i+1)
                    hp.remove();
                
                j++;
                i++;
            }   
        }
        return res;       
    }
    class pair implements Comparable<pair>{
        int val;
        int key;
        pair(int k,int v){
            key=k;
            val=v;
        }
        
        @Override
        public int compareTo(pair o){
            return o.val-this.val;
        }
    }
-------------------------------------------------------------------------------------------------
8. Kth Largest Contiguous SubarraySum )(n^2logk)
public static void kthlargestSubarraySum(int[] arr, int k) {
		PriorityQueue<Integer> hp = new PriorityQueue<>();
		int[] sum = new int[arr.length + 1];
		sum[1] = arr[0];
		for (int i = 2; i < sum.length; i++) {
			sum[i] = sum[i - 1] + arr[i - 1];
		}

		for (int i = 1; i < sum.length; i++) {
			for (int j = i; j < sum.length; j++) {
				int x = sum[j] - sum[i - 1];

				if (hp.size() < k) {
					hp.add(x);
				} else {
					if (hp.peek() < x) {
						hp.remove();
						hp.add(x);
					}
				}
			}
		}
		System.out.println(hp.peek());
	}
-------------------------------------------------------------------------------------------------
9. Merge two binary Max heaps 
Logic-> copy both arrays in resultant array and apply heapify function .
-------------------------------------------------------------------------------------------------
10. Is Binary Tree Heap
public boolean isBTHeapt(Node node,int size,int idx){
        if(node==null)
            return true;
        if(node.left!=null && node.left.data>node.data||node.right!=null && node.right.data>node.data)
            return false;
            
        if(idx>=size)
            return false;
        
        return isBTHeapt(node.left,size,2*idx+1)&&isBTHeapt(node.right,size,2*idx+2);
    }
-------------------------------------------------------------------------------------------------
11. Minimum sum of two numbers formed from digits of an array
-> sort the array take two strings add alternate digits to string, eg) s1 contains all odd digits , s2 contains all even digits, (this could be done using Min heap) now add two strings just like adding 2 arrays
--->
public static void sumof2arrays(int[] a1, int[] a2) {
		int i = a1.length - 1;
		int j = a2.length - 1;
		int carry = 0;
		ArrayList<Integer> ans = new ArrayList<Integer>();
		while (i >= 0 || j >= 0) {
			int sum = carry;
			if (i >= 0) {
				sum += a1[i];
				i--;
			}
			if (j >= 0) {
				sum += a2[j];
				j--;
			}

			int rem = sum % 10;
			carry = sum / 10;
			ans.add(0, rem);
		}
		if (carry > 0) {
			ans.add(0, carry);
		}
		for (int k = 0; k < ans.size(); k++) {
			System.out.print(ans.get(k) + " ");
		}
	}
-------------------------------------------------------------------------------------------------
12. Smallest Range Covering Elements from K lists
  public int[] smallestRange(List<List<Integer>> nums) {
        int[]ans=new int[2];
        PriorityQueue<pair>pq=new PriorityQueue<>((a,b)->a.data-b.data);
        
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        int range=Integer.MAX_VALUE;
        int l=0;
        int h=0;
       for(int i=0;i<nums.size();i++){
           int a=nums.get(i).get(0);
           max=Math.max(max,a);
           min=Math.min(min,a);
           pair np=new pair(a,i,0,nums.get(i).size());
           pq.add(np);
       }
        
        while(!pq.isEmpty()){
            pair rp=pq.poll();
            int maybemin=rp.data;
            if(range>max-maybemin){
                min=maybemin;
                range=max-min;
                l=min;
                h=max;
            }
            
            if(rp.idx+1==rp.arraysize)
                break; //because my range can't be altered further
            
               rp.idx++;
               rp.data=nums.get(rp.listno).get(rp.idx);
                max=Math.max(rp.data,max);
                min=Math.min(rp.data,min);   //no need to calculate this because we are shifting from min to max
               pq.add(rp);             
        }    
        ans[0]=l;
        ans[1]=h;
        return ans;
    }
    class pair{
        int data;
        int listno;
        int idx;
        int arraysize;
        pair(int d,int l,int i,int s){
            data=d;
            listno=l;
            idx=i;
            arraysize=s;
        }
    }
-------------------------------------------------------------------------------------------------
13. Convert Min Heap to Max Heap (Looks like nlogn but it is N only)
Logic-> Just create max heap from the given array using heapify fxn, that's it
-------------------------------------------------------------------------------------------------
14. Convert Bst to Min Heap
Logic-> Add all the elements from inorder traversal of bst then traverse preorder and copy all elements to node.
Input :          4
               /   \
              2     6
            /  \   /  \
           1   3  5    7  

Output :        1
              /   \
             2     5
           /  \   /  \
          3   4  6    7 
-------------------------------------------------------------------------------------------------
15. Minimum Cost of Ropes
long minCost(long arr[], int n) 
    {
       PriorityQueue<Long> hp = new PriorityQueue<>();
        for(int i=0;i<arr.length;i++){
            hp.add(arr[i]);
        }
        long cost=0;
        while(hp.size()>1){
            long a=hp.remove();
            long b=hp.remove();
            cost+=a+b;
            hp.add(a+b);
        }
        return cost;
    }
-------------------------------------------------------------------------------------------------
16. Find the median from data Stream
 PriorityQueue<Integer> max; //left priority queue is max heap
    PriorityQueue<Integer> min; //right priority queue is min heap
    
    public MedianFinder() {
        max=new PriorityQueue<>(Comparator.reverseOrder());
        min=new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if(max.isEmpty()&&min.isEmpty()){
            max.add(num);
        }else if(num > max.peek()){
            min.add(num);
            if(min.size()-max.size()>=2){
                max.add(min.remove());
            }
        }else{
            max.add(num);
            if(max.size()-min.size()>=2){
                min.add(max.remove());
            }
        }
    }
    
    public double findMedian() {
        if(max.size()==min.size()){
            double ans=(double)max.peek()+(double)min.peek();
            ans=ans/(double)2;
            return ans;
        }
        if(max.size()<min.size()){
            return (double)min.peek();
        }
        return (double)max.peek();
    }

# Very Similar problem 
-> Sliding Window Median (Leetcode 480)
 

    //Not taking PriorityQueue because it will take o(k) time in removal of element other than peek
    //But TreeSet take O(logK) in the worst case also.
    // Storing indexes not values just to maintain order of the duplicates too.
    
    public double[] medianSlidingWindow(int[] nums, int k) {
        double[]res = new double[nums.length-k+1];
        
	// Basically both are in ascending order and for lo we find max through last element.
	// for hi we find min through first element
        TreeSet<Integer>lo = new TreeSet<>((a,b)->nums[a]!=nums[b]?Integer.compare(nums[a],nums[b]):a-b);    
        TreeSet<Integer>hi = new TreeSet<>((a,b)->nums[a]!=nums[b]?Integer.compare(nums[a],nums[b]):a-b);
        
        int right=0,left=0;
        
        while(left<nums.length){
            // Did below 3 lines just to maintain the size just like in heap we maintained when finding meadian of data stream.
            lo.add(left);
            hi.add(lo.pollLast());
            if(hi.size()>lo.size())lo.add(hi.pollFirst());
            
            if(lo.size()+hi.size()==k){
                res[right]=(lo.size()==hi.size())?nums[lo.last()]/2.0+nums[hi.first()]/2.0:nums[lo.last()]/1.0;
                
                if(!lo.remove(right))hi.remove(right); //checking window
                right++;
            }
            left++;
        }
        return res;
    }

-------------------------------------------------------------------------------------------------
17. Furtheset Building you can reach

-> The optimal way of going forward requires us to use ladders for gaps that are larger than others and use bricks for the rest.
So we just need to maintain a min heap during the scan and keep its size smaller than number of ladders. Once the size of heap is larger than the number of ladders, that means we need to use bricks for the smallest gap in the heap.
    
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        
        PriorityQueue<Integer>pq = new PriorityQueue<>();
        
        for(int i=1;i<heights.length;i++){
            int diff = heights[i]-heights[i-1];
            
            if(diff<=0)continue;  //next height is smaller so just jump
            
            pq.add(diff);
            
            if(pq.size()>ladders){ //means all ladders have been used in heights now for the lowest heights diff using bricks
                bricks-=pq.poll();
            }
            
            if(bricks<0)return i-1;
        }
        
        return heights.length-1;
    }
-------------------------------------------------------------------------------------------------