library/cpp/containers/limited_heap/limited_heap.h


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

#pragma once

#include <util/generic/queue.h>
#include <util/generic/algorithm.h>

template <class T, class TComparator = TGreater<T>>
class TLimitedHeap {
private:
    size_t MaxSize;
    TComparator Comparer;
    TPriorityQueue<T, TVector<T>, TComparator> Internal;

public:
    TLimitedHeap(size_t maxSize, const TComparator& comp = TComparator())
        : MaxSize(maxSize)
        , Comparer(comp)
        , Internal(Comparer)
    {
        Y_ASSERT(maxSize >= 1);
    }

    const T& GetMin() const {
        return Internal.top();
    }

    void PopMin() {
        Internal.pop();
    }

    bool Insert(const T& value) {
        if (GetSize() == MaxSize) {
            if (Comparer(GetMin(), value)) {
                return false;
            } else {
                PopMin();
            }
        }

        Internal.push(value);

        return true;
    }

    bool IsEmpty() const {
        return Internal.empty();
    }

    size_t GetSize() const {
        return Internal.size();
    }

    size_t GetMaxSize() const {
        return MaxSize;
    }

    void SetMaxSize(size_t newMaxSize) {
        while (GetSize() > newMaxSize) {
            PopMin();
        }
        MaxSize = newMaxSize;
    }
};