#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;
//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+IGl0ZW0pewoJCQlwcVtsb2NhdGlvbiArIDFdID0gcHFbbG9jYXRpb25dOwoJCQlsb2NhdGlvbiA9IGxvY2F0aW9uIC0gMTsKCQl9CgkJcHFbbG9jYXRpb24gKyAxXSA9IGl0ZW07CgkJLy9wcVtuKytdID0gaXRlbTsKCX0KCglJdGVtIGdldG1heCgpewoJCWludCBtYXggPSAwOwoKCQlmb3IoaW50IGkgPSAxOyBpIDwgbjsgaSsrKQoJCQlpZihwcVttYXhdIDwgcHFbaV0pCgkJCQltYXggPSBpOwoJCXN0ZDo6c3dhcChwcVttYXhdLCBwcVtuLTFdKTsKCQlyZXR1cm4gcHFbLS1uXTsKCX0KCglJdGVtIGdldG1pbigpewoJCWludCBtaW4gPSAwOwoKCQlmb3IoaW50IGkgPSAxOyBpIDwgbjsgaSsrKQoJCQlpZihwcVttaW5dID4gcHFbaV0pCgkJCQltaW4gPSBpOwoJCXN0ZDo6c3dhcChwcVttaW5dLCBwcVtuLTFdKTsKCQlyZXR1cm4gcHFbLS1uXTsKCX0KCgl2b2lkIHNob3coKXsKCQlmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQoJCQlwcVtpXS5wcmludCgpOwoJfQp9OwoKaW50IG1haW4oKXsKCWludCBwOzsKCVBRPEl0ZW0+IHBxKDUwKTsKCQoJZm9yKGludCBpID0gMDsgaSA8IDEwOyBpKyspCgkJcHEuaW5zZXJ0KEl0ZW0oNywgaSkpOwoKCXBxLnNob3coKTsKCglzdGQ6OmNvdXQgPDwgIm1heDogIjsKCXBxLmdldG1heCgpLnByaW50KCk7CglzdGQ6OmNvdXQgPDwgIm1heDogIjsKCXBxLmdldG1heCgpLnByaW50KCk7CglzdGQ6OmNvdXQgPDwgIm1pbjogIjsKCXBxLmdldG1pbigpLnByaW50KCk7CglzdGQ6OmNvdXQgPDwgIm1pbjogIjsKCXBxLmdldG1pbigpLnByaW50KCk7CgoJc3RkOjpjaW4gPj4gcDsKCXJldHVybiAwOwp9