1import java.util.PriorityQueue;
2
3// Class to find the kth largest element in a stream of numbers
4class KthLargest {
5
6    // Priority queue to maintain the smallest 'k' elements seen so far
7    private PriorityQueue<Integer> minHeap;
8
9    // The kth position we are interested in for the largest element
10    private int k;
11
12    /**
13     * Constructor to initialize the data structure and populate with initial elements.
14     *
15     * @param k    The kth position to track in the list of largest elements.
16     * @param nums An array of initial numbers to be added to the kth largest tracker.
17     */
18    public KthLargest(int k, int[] nums) {
19        // Initialize a min-heap with the capacity to hold 'k' elements
20        this.minHeap = new PriorityQueue<>(k);
21        this.k = k;
22
23        // Add the initial elements to the kth largest tracker
24        for (int num : nums) {
25            add(num);
26        }
27    }
28
29    /**
30     * Adds a new number into the stream and returns the kth largest element.
31     *
32     * @param val The new number to be added to the stream.
33     * @return The kth largest element after adding the new number.
34     */
35    public int add(int val) {
36        // Always add the new value to the min-heap
37        minHeap.offer(val);
38
39        // If the size of the min-heap exceeds 'k', remove the smallest element
40        if (minHeap.size() > k) {
41            minHeap.poll();
42        }
43
44        // The root of the min-heap represents the kth largest element
45        return minHeap.peek();
46    }
47}
48
49/* Usage example:
50 * KthLargest kthLargest = new KthLargest(3, new int[]{4, 5, 8, 2});
51 * kthLargest.add(3);   // returns 4
52 * kthLargest.add(5);   // returns 5
53 * kthLargest.add(10);  // returns 5
54 * kthLargest.add(9);   // returns 8
55 * kthLargest.add(4);   // returns 8
56 */
57

1#include <queue>
2#include <vector>
3
4// Define a class to find kth largest element in a stream of numbers.
5class KthLargest {
6public:
7    // Declare a min heap to keep track of the k largest elements.
8    std::priority_queue<int, std::vector<int>, std::greater<>> minHeap;
9    // Store the value of 'k' to know which largest element to keep track of.
10    int kthSize;
11
12    // Constructor for initializing the KthLargest class.
13    // k - The kth position to track.
14    // nums - Initial list of numbers from which we find the kth largest element.
15    KthLargest(int k, std::vector<int>& nums) {
16        kthSize = k;
17        // Add initial numbers to the heap
18        for (int num : nums) {
19            add(num);
20        }
21    }
22
23    // Function to add a number to the stream and return the kth largest element.
24    int add(int val) {
25        // Add the new number to the min heap.
26        minHeap.push(val);
27        // If the heap size is greater than k, remove the smallest element.
28        if (minHeap.size() > kthSize) {
29            minHeap.pop();
30        }
31        // Return the kth largest element (top of the min heap).
32        return minHeap.top();
33    }
34};
35
36/**
37 * The provided code snippet illustrates the use of the KthLargest class.
38 * It demonstrates the instantiation of a KthLargest object and subsequent calls to its add method.
39 */
40

1type ComparatorFunction = (a: number, b: number) => number;
2
3let kthLargestSize: number;
4let minHeap: MinHeap;
5
6interface MinHeap {
7    data: number[];
8    comparator: ComparatorFunction;
9    heapify: () => void;
10    peek: () => number | null;
11    offer: (value: number) => void;
12    poll: () => number | null;
13    bubbleUp: (index: number) => void;
14    bubbleDown: (index: number) => void;
15    swap: (index1: number, index2: number) => void;
16    size: () => number;
17}
18
19// Initializing the Kth largest element finder
20function KthLargestInit(k: number, nums: number[]): void {
21    kthLargestSize = k;
22    minHeap = createMinHeap();
23    nums.forEach(num => {
24        kthLargestAdd(num);
25    });
26}
27
28// Function to add a new value to the data collection
29function kthLargestAdd(val: number): number {
30    minHeap.offer(val);
31    if (minHeap.size() > kthLargestSize) {
32        minHeap.poll();
33    }
34    return minHeap.peek()!;
35}
36
37// Create a MinHeap with default values and a comparator
38function createMinHeap(): MinHeap {
39    const heap: MinHeap = {
40        data: [],
41        comparator: (a, b) => a - b,
42        heapify() {
43            if (this.size() < 2) return;
44            for (let i = 1; i < this.size(); i++) {
45                this.bubbleUp(i);
46            }
47        },
48        peek() {
49            return this.size() === 0 ? null : this.data[0];
50        },
51        // Adds a new value and bubbles it up to maintain heap property
52        offer(value) {
53            this.data.push(value);
54            this.bubbleUp(this.size() - 1);
55        },
56        // Removes and returns the root value of the heap
57        poll() {
58            if (this.size() === 0) {
59                return null;
60            }
61            const result = this.data[0];
62            const last = this.data.pop();
63            if (this.size() !== 0) {
64                this.data[0] = last!;
65                this.bubbleDown(0);
66            }
67            return result;
68        },
69        // Bubbles a value up the heap until the heap property is restored
70        bubbleUp(index) {
71            while (index > 0) {
72                const parentIndex = (index - 1) >> 1;
73                if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
74                    this.swap(index, parentIndex);
75                    index = parentIndex;
76                } else {
77                    break;
78                }
79            }
80        },
81        // Bubbles a value down the heap until the heap property is restored
82        bubbleDown(index) {
83            const lastIndex = this.size() - 1;
84            while (true) {
85                let findIndex = index;
86                const leftIndex = index * 2 + 1;
87                const rightIndex = index * 2 + 2;
88                if (
89                    leftIndex <= lastIndex &&
90                    this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
91                ) {
92                    findIndex = leftIndex;
93                }
94                if (
95                    rightIndex <= lastIndex &&
96                    this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
97                ) {
98                    findIndex = rightIndex;
99                }
100                if (index !== findIndex) {
101                    this.swap(index, findIndex);
102                    index = findIndex;
103                } else {
104                    break;
105                }
106            }
107        },
108        // Swaps two values in the heap
109        swap(index1, index2) {
110            [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
111        },
112        // Returns the number of elements in the heap
113        size() {
114            return this.data.length;
115        }
116    };
117
118    heap.heapify();
119    return heap;
120}
121
122// Example of usage
123KthLargestInit(3, [4, 5, 8, 2]);
124console.log(kthLargestAdd(3)); // Should return the kth largest element after adding 3
125console.log(kthLargestAdd(5)); // Should return the kth largest element after adding 5
126console.log(kthLargestAdd(10)); // Should return the kth largest element after adding 10
127console.log(kthLargestAdd(9)); // Should return the kth largest element after adding 9
128console.log(kthLargestAdd(4)); // Should return the kth largest element after adding 4
129