#include <iostream>
class Item{
private:
int key;
int data;
public:
Item(): data(0), key(0){}
Item(int data, int key): data(data), key(key){}
void print(){
std::cout << "data: " << data << ", key " << key << std::endl;
}
bool operator <(const Item &item){ return key < item.key; }
bool operator >(const Item &item){ return key > item.key; }
};
template<class Item>
class PQ{
private:
Item *pq; /*Массив элементов*/
int n; /*Текущее оличество элементов в очереди*/
public:
PQ(int max){
pq = new Item[max];
n = 0;
}
int empty() const{ return n == 0; }
void insert(Item item){
int location = n - 1;
while(location >= 0 && pq[location] > item){
pq[location + 1] = pq[location];
location = location - 1;
}
pq[location + 1] = item;
n++;
//pq[n++] = item;
}
Item getmax(){
int max = 0;
for(int i = 1; i < n; i++)
if(pq[max] < pq[i])
max = i;
std::swap(pq[max], pq[n-1]);
return pq[--n];
}
Item getmin(){
int min = 0;
for(int i = 1; i < n; i++)
if(pq[min] > pq[i])
min = i;
std::swap(pq[min], pq[n-1]);
return pq[--n];
}
void show(){
for(int i = 0; i < n; i++)
pq[i].print();
}
};
int main(){
int p;;
PQ<Item> pq(50);
for(int i = 0; i < 10; i++)
pq.insert(Item(7, i));
pq.show();
std::cout << "max: ";
pq.getmax().print();
std::cout << "max: ";
pq.getmax().print();
std::cout << "min: ";
pq.getmin().print();
std::cout << "min: ";
pq.getmin().print();
std::cin >> p;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKY2xhc3MgSXRlbXsKcHJpdmF0ZToKCWludCBrZXk7CglpbnQgZGF0YTsKcHVibGljOgoJSXRlbSgpOiBkYXRhKDApLCBrZXkoMCl7fQoJSXRlbShpbnQgZGF0YSwgaW50IGtleSk6IGRhdGEoZGF0YSksIGtleShrZXkpe30KCXZvaWQgcHJpbnQoKXsKCQlzdGQ6OmNvdXQgPDwgImRhdGE6ICIgPDwgZGF0YSA8PCAiLCBrZXkgIiA8PCBrZXkgPDwgc3RkOjplbmRsOwoJfQoJYm9vbCBvcGVyYXRvciA8KGNvbnN0IEl0ZW0gJml0ZW0peyByZXR1cm4ga2V5IDwgaXRlbS5rZXk7IH0KCWJvb2wgb3BlcmF0b3IgPihjb25zdCBJdGVtICZpdGVtKXsgcmV0dXJuIGtleSA+IGl0ZW0ua2V5OyB9Cn07Cgp0ZW1wbGF0ZTxjbGFzcyBJdGVtPgpjbGFzcyBQUXsKcHJpdmF0ZToKCUl0ZW0gKnBxOwkvKtCc0LDRgdGB0LjQsiDRjdC70LXQvNC10L3RgtC+0LIqLwoJaW50IG47CQkvKtCi0LXQutGD0YnQtdC1INC+0LvQuNGH0LXRgdGC0LLQviDRjdC70LXQvNC10L3RgtC+0LIg0LIg0L7Rh9C10YDQtdC00LgqLwpwdWJsaWM6CglQUShpbnQgbWF4KXsKCQlwcSA9IG5ldyBJdGVtW21heF07CgkJbiA9IDA7Cgl9CgoJaW50IGVtcHR5KCkgY29uc3R7IHJldHVybiBuID09IDA7IH0KCgl2b2lkIGluc2VydChJdGVtIGl0ZW0pewoJCWludCBsb2NhdGlvbiA9IG4gLSAxOwoKCQl3aGlsZShsb2NhdGlvbiA+PSAwICYmIHBxW2xvY2F0aW9uXSA+IGl0ZW0pewoJCQlwcVtsb2NhdGlvbiArIDFdID0gcHFbbG9jYXRpb25dOwoJCQlsb2NhdGlvbiA9IGxvY2F0aW9uIC0gMTsKCQl9CgkJcHFbbG9jYXRpb24gKyAxXSA9IGl0ZW07CgkJbisrOwoJCS8vcHFbbisrXSA9IGl0ZW07Cgl9CgoJSXRlbSBnZXRtYXgoKXsKCQlpbnQgbWF4ID0gMDsKCgkJZm9yKGludCBpID0gMTsgaSA8IG47IGkrKykKCQkJaWYocHFbbWF4XSA8IHBxW2ldKQoJCQkJbWF4ID0gaTsKCQlzdGQ6OnN3YXAocHFbbWF4XSwgcHFbbi0xXSk7CgkJcmV0dXJuIHBxWy0tbl07Cgl9CgoJSXRlbSBnZXRtaW4oKXsKCQlpbnQgbWluID0gMDsKCgkJZm9yKGludCBpID0gMTsgaSA8IG47IGkrKykKCQkJaWYocHFbbWluXSA+IHBxW2ldKQoJCQkJbWluID0gaTsKCQlzdGQ6OnN3YXAocHFbbWluXSwgcHFbbi0xXSk7CgkJcmV0dXJuIHBxWy0tbl07Cgl9CgoJdm9pZCBzaG93KCl7CgkJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKCQkJcHFbaV0ucHJpbnQoKTsKCX0KfTsKCmludCBtYWluKCl7CglpbnQgcDs7CglQUTxJdGVtPiBwcSg1MCk7CgkKCWZvcihpbnQgaSA9IDA7IGkgPCAxMDsgaSsrKQoJCXBxLmluc2VydChJdGVtKDcsIGkpKTsKCglwcS5zaG93KCk7CgoJc3RkOjpjb3V0IDw8ICJtYXg6ICI7CglwcS5nZXRtYXgoKS5wcmludCgpOwoJc3RkOjpjb3V0IDw8ICJtYXg6ICI7CglwcS5nZXRtYXgoKS5wcmludCgpOwoJc3RkOjpjb3V0IDw8ICJtaW46ICI7CglwcS5nZXRtaW4oKS5wcmludCgpOwoJc3RkOjpjb3V0IDw8ICJtaW46ICI7CglwcS5nZXRtaW4oKS5wcmludCgpOwoKCXN0ZDo6Y2luID4+IHA7CglyZXR1cm4gMDsKfQ==
data: 7, key 0
data: 7, key 1
data: 7, key 2
data: 7, key 3
data: 7, key 4
data: 7, key 5
data: 7, key 6
data: 7, key 7
data: 7, key 8
data: 7, key 9
max: data: 7, key 9
max: data: 7, key 8
min: data: 7, key 0
min: data: 7, key 1