assign/extractmin.cpp at master · pradg73/assign · 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//extract min
#include <bits/stdc++.h>
using namespace std;

struct MinS{

    stack<int> orders;
    multiset<int> minmap, delmap;

    void addOrder(int i){
        orders.push(i);
        minmap.insert(i);
    }

    int executeOrder(){
        int i = orders.top();
        orders.pop();
        delmap.insert(i);
        return i;

    }

    int extractMin(){

        while(1){
        auto itm = minmap.begin();

        auto itd = delmap.find(*itm);

        if (itd != delmap.end()){
            minmap.erase(itm); delmap.erase(itd);
        }else{
            return *itm;
        }
        }
    }

};

int  main(){

    MinS s;
    /*
    addOrder(13), addOrder(11), addOrder(9), addOrder(20)
extractMin() -> 9

executeOrder() -> 20
extractMin() -> 9

executeOrder() -> 9
extractMin() -> 11

addOrder(11)
extractMin() -> 11

executeOrder() -> 11
extractMin() -> 11

executeOrder() -> 11
extractMin() -> 13

executeOrder() -> 13*/

    s.addOrder(13);
    s.addOrder(11);
    s.addOrder(9);
    s.addOrder(20);

    cout << s.extractMin() <<  '\n';// -> 9

    cout << s.executeOrder() << '\n'; //-> 20
    cout << s.extractMin() << '\n'; // -> 9

    cout << s.executeOrder() << '\n'; // -> 9
    cout << s.extractMin() << '\n'; //-> 11

    s.addOrder(11);
    cout << s.extractMin() << '\n'; // -> 11

    cout << s.executeOrder() << '\n'; //-> 11
    cout << s.extractMin() << '\n'; //-> 11

    cout << s.executeOrder() << '\n'; //-> 11
    cout << s.extractMin() << '\n'; //-> 13

    cout << s.executeOrder() << '\n'; //-> 13
    return 0;
}