```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)
```#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());

// 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>();

// 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);
}

} ```
star

Sat Aug 13 2022 21:49:52 GMT+0000 (UTC) https://leetcode.com/problems/kth-largest-element-in-a-stream/

#python #leetcode #neetcode #stream #heap
star

Tue Aug 09 2022 23:23:42 GMT+0000 (UTC) https://www.educative.io/courses/grokking-the-coding-interview/RM535yM9DW0

#python #heap #top #k #max