leetcode/code/703.kth-largest-element-in-a-stream.cpp at main · SocioDroid/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class KthLargest {
public:
    vector<int> heap;
    int k;
    KthLargest(int k, vector<int>& nums) {
        this->k = k;

        for(int i: nums)
            cout<<add(i)<<endl;
    }

    int add(int val) {
        if(heap.size() < k){
            heap.push_back(val);
            heapify_bottom(heap.size() - 1);

        }
        else if(heap[0] < val)
        {
            heap[0] = val;
            heapify(0);

        }
        return heap[0];
    }

    void heapify(int i){
        if(i > heap.size())
            return;

        int max_index = i;
        int lc = (2*i) + 1;
        int rc = (2*i) + 2;

        if(lc < heap.size() && heap[lc] < heap[max_index])
            max_index = lc;


        if(rc < heap.size() && heap[rc] < heap[max_index])
            max_index = rc;


        if(max_index != i){
            swap(heap[i], heap[max_index]);
            heapify(max_index);
        }
        return;
    }
    void heapify_bottom(int i){
        int parent = (i-1)/2;


        if(parent > -1 && heap[parent] > heap[i]){
            swap(heap[parent], heap[i]);
            heapify_bottom(parent);
        }
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */