class KthLargest:
	
    #Big O: n 
    def __init__(self, k: int, nums: List[int]): 
        #minHeap with k largest integers 
        
        self.minHeap, self.k = nums, k 
        heapq.heapify(self.minHeap) 
        
        while len(self.minHeap) > k: 
            heapq.heappop(self.minHeap) 
            
        

    #Big O: log N 
    def add(self, val: int) -> int:
        heapq.heappush(self.minHeap, val) 
        
        if len(self.minHeap) > self.k: 
            heapq.heappop(self.minHeap)
        
        return self.minHeap[0]
    

#Total big O: n log n 
    
    
    
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

#solution involving minHeap 
#Strategy: 
#1) Take out the smallest number from the heap, and
#2) Insert the larger number into the heap.
#3) repeat 
#This will ensure that we always have ‘K’ largest numbers in the heap. The most efficient way to repeatedly find the smallest number among a set of numbers will be to use a min-heap.


#Big O n log k. Space: O (k) 

from heapq import *
#this is a heap library. look at relevant functions: https://docs.python.org/3/library/heapq.html 


def find_k_largest_numbers(nums, k):
  minHeap = []
  # put first 'K' numbers in the min heap
  for i in range(k):
    heappush(minHeap, nums[i])

  # go through the remaining numbers of the array, if the number from the array is bigger than the
  # top(smallest) number of the min-heap, remove the top number from heap and add the number from array
  for i in range(k, len(nums)):
    if nums[i] > minHeap[0]:
    #heapop removes smallest element in heap 
      heappop(minHeap)
      heappush(minHeap, nums[i])

  # the heap has the top 'K' numbers
  return minHeap


#brute force approach has big O of n log N 
def find_k_largest_numbers(nums, k):
  result = []
  
  nums.sort() 
  nums_length_index = len(nums) - 1 - k 

  for i in range(nums_length_index + 1, len(nums)): 
    result.append(nums[i]) 
  
  return result

find_k_largest_numbers([3, 1, 5, 12, 2, 12], 3) # will result in [5, 12, 12] 


#if you dont want duplicates you can do the following: 
def find_k_largest_numbers(nums, k):
  result = []
  
  nums.sort() 
  nums_set = set(nums)
  nums_length_index = len(nums_set) - 1 - k 

  for i in range(nums_length_index + 1, len(nums_set)): 
    result.append(nums[i]) 
  
  return result

// Max Heap:

// Java program to demonstrate working of PriorityQueue in Java
import java.util.*;

class Test{
    public static void main(String args[])
    {
        // Creating empty priority queue
        PriorityQueue<Integer> pq 
        = new PriorityQueue<Integer>(
            Collections.reverseOrder());

        // Adding items to the pQueue using add()
        pq.add(10);
        pq.add(20);
        pq.add(15);
        
        // Above PriorityQueue is stored as following
        //       20
        //      /  \
        //    10    15

        // Printing the top element of PriorityQueue
        System.out.println(pq.peek());

        // Printing the top element and removing it
        // from the PriorityQueue container
        System.out.println(pq.poll());

        // Post poll() PriorityQueue looks like
        //       15
        //      /  
        //    10   

        // Printing the top element again
        System.out.println(pq.peek());
    }
}

// OUTPUT : 
10
10
15










// Min Heap(default)

// Java program to demonstrate working of PriorityQueue in Java
import java.util.*;

class Test{
    public static void main(String args[])
    {
        // Creating empty priority queue
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        // Adding items to the pQueue using add()
        pq.add(10);
        pq.add(20);
        pq.add(15);
        
       
        // Printing the top element of PriorityQueue
        System.out.println(pq.peek());

        // Printing the top element and removing it
        // from the PriorityQueue container
        System.out.println(pq.poll());


        // Printing the top element again
        System.out.println(pq.peek());
    }
}

// OUTPUT : 
20
20
15

import java.util.*;
import java.io.*;
  
public class HeapSort 
{ 
	public void buildheap(int arr[], int n){
        for (int i = n / 2 - 1; i >= 0; i--) 
		    heapify(arr, n, i);
    }
	
	public void sort(int arr[]) 
	{ 
		int n = arr.length; 

		buildheap(arr,n); 
 
		for (int i=n-1; i>0; i--) 
		{ 
			 
			int temp = arr[0]; 
			arr[0] = arr[i]; 
			arr[i] = temp; 

			heapify(arr, i, 0); 
		} 
	} 

	void heapify(int arr[], int n, int i) 
	{ 
		int largest = i;  
		int l = 2*i + 1; 
		int r = 2*i + 2; 

		if (l < n && arr[l] > arr[largest]) 
			largest = l; 
 
		if (r < n && arr[r] > arr[largest]) 
			largest = r; 

		if (largest != i) 
		{ 
			int swap = arr[i]; 
			arr[i] = arr[largest]; 
			arr[largest] = swap; 

			heapify(arr, n, largest); 
		} 
	} 

	static void printArray(int arr[]) 
	{ 
		int n = arr.length; 
		for (int i=0; i<n; ++i) 
			System.out.print(arr[i]+" "); 
		System.out.println(); 
	} 
 
	public static void main(String args[]) 
	{ 
		int arr[] = {12, 11, 13, 5, 6, 7}; 
		int n = arr.length; 

		HeapSort ob = new HeapSort(); 
		ob.sort(arr); 

		System.out.println("Sorted array is"); 
		printArray(arr); 
	} 
} 

import java.util.*;
import java.io.*;
  
class Test {
    
    public static class MinHeap{
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    
        public void minHeapify(int i) 
        { 
            int lt = left(i); 
            int rt = right(i); 
            int smallest = i; 
            if (lt < size && arr[lt] < arr[i]) 
                smallest = lt; 
            if (rt < size && arr[rt] < arr[smallest]) 
                smallest = rt; 
            if (smallest != i) 
            { 
                int temp = arr[i]; 
                arr[i] = arr[smallest]; 
                arr[smallest] = temp; 
                minHeapify(smallest); 
            } 
        }
    
        public void buildHeap(){
            for(int i=(size-2)/2;i>=0;i--)
                minHeapify(i);
        }
    
    }
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
    } 
   
} 

import java.util.*;
import java.io.*;
  
class Test {
    
    public static class MinHeap{
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    
    
        public void insert(int x) 
        { 
            if (size == capacity)return;
            size++; 
            arr[size-1]=x; 
         
            for (int i=size-1;i!=0 && arr[parent(i)]>arr[i];) 
            { 
               int temp = arr[i]; 
                arr[i] = arr[parent(i)]; 
                arr[parent(i)] = temp; 
               i = parent(i); 
            } 
        }
    
        public void minHeapify(int i) 
        { 
            int lt = left(i); 
            int rt = right(i); 
            int smallest = i; 
            if (lt < size && arr[lt] < arr[i]) 
                smallest = lt; 
            if (rt < size && arr[rt] < arr[smallest]) 
                smallest = rt; 
            if (smallest != i) 
            { 
                int temp = arr[i]; 
                arr[i] = arr[smallest]; 
                arr[smallest] = temp; 
                minHeapify(smallest); 
            } 
        }
    
        public int extractMin() 
        { 
            if (size <= 0) 
                return Integer.MAX_VALUE; 
            if (size == 1) 
            { 
                size--; 
                return arr[0]; 
            }  
            int temp = arr[0]; 
            arr[0] = arr[size-1]; 
            arr[size-1] = temp;
            size--; 
            minHeapify(0); 
          
            return arr[size]; 
        }
    
        void decreaseKey(int i, int x) 
        { 
            arr[i] = x; 
            while (i != 0 && arr[parent(i)] > arr[i]) 
            { 
               int temp = arr[i]; 
               arr[i] = arr[parent(i)]; 
               arr[parent(i)] = temp; 
               i = parent(i); 
            } 
        }
    
        void deleteKey(int i) 
        { 
            decreaseKey(i, Integer.MIN_VALUE); 
            extractMin(); 
        }
    
    }
    
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
        h.insert(3); 
        h.insert(2);
        h.deleteKey(0);
        h.insert(15);
        h.insert(20);
        System.out.println(h.extractMin());
        h.decreaseKey(2, 1);
        System.out.println(h.extractMin());
    } 
} 

import java.util.*;
import java.io.*;
  
class Test {
    
    public static class MinHeap
    {
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    
    
        public void insert(int x) 
        { 
            if (size == capacity)return;
            size++; 
            arr[size-1]=x; 
         
            for (int i=size-1;i!=0 && arr[parent(i)]>arr[i];) 
            { 
                int temp = arr[i]; 
                arr[i] = arr[parent(i)]; 
                arr[parent(i)] = temp; 
                i = parent(i); 
            } 
        }
    
        public void minHeapify(int i) 
        { 
            int lt = left(i); 
            int rt = right(i); 
            int smallest = i; 
            if (lt < size && arr[lt] < arr[i]) 
                smallest = lt; 
            if (rt < size && arr[rt] < arr[smallest]) 
                smallest = rt; 
            if (smallest != i) 
            { 
                int temp = arr[i]; 
                arr[i] = arr[smallest]; 
                arr[smallest] = temp; 
                minHeapify(smallest); 
            } 
        }
    
        public int extractMin() 
        { 
            if (size <= 0) 
                return Integer.MAX_VALUE; 
            if (size == 1) 
            { 
                size--; 
                return arr[0]; 
            }  
            int temp = arr[0]; 
            arr[0] = arr[size-1]; 
            arr[size-1] = temp;
            size--; 
            minHeapify(0); 
          
            return arr[size]; 
        } 
        
    }
    
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
        h.insert(3); 
        h.insert(2);
        h.insert(15);
        h.insert(20);
        System.out.print(h.extractMin());     // OUTPUT : 2
    } 
} 

import java.util.*;
import java.io.*;
  
class Test {
    
    public static class MinHeap{
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    
    
        public void insert(int x) 
        { 
            if (size == capacity)return;
            size++; 
            arr[size-1]=x; 
         
            for (int i=size-1;i!=0 && arr[parent(i)]>arr[i];) 
            { 
               int temp = arr[i]; 
                arr[i] = arr[parent(i)]; 
                arr[parent(i)] = temp; 
               i = parent(i); 
            } 
        }
    
    }
    
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
        h.insert(3); 
        h.insert(2);
        h.insert(15);
        h.insert(20);
    } 
   
} 

import java.util.*;
import java.io.*;
  
class Test { 
    
    public static class MinHeap{
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    }
    
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
    } 
   
}