Pagini recente » Borderou de evaluare (job #634384) | Cod sursa (job #1254937) | Cod sursa (job #1183350)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
template <typename T>
class Heap {
T* values;
T* v;
int dimVect;
int capVect;
public:
Heap(int capVect) {
this->capVect = capVect;
dimVect = 0;
values = new T[capVect];
v = new T[100000000];
}
~Heap() {
delete[] values;
}
int parent(int poz) {
if (poz > 0) {
return (poz - 1) / 2;
}
else
return -1;
}
int leftSubtree(int poz) {
if (2 * poz + 1 <= dimVect)
return 2 * poz + 1;
else
return -1;
}
int rightSubtree(int poz) {
if (2 * poz + 2 <= dimVect)
return 2 * poz + 2;
else
return -1;
}
void pushUp(int poz) {
int indice = parent(poz);
if (indice == - 1)
return;
if (values[indice] > values[poz]) {
T aux;
aux = values[poz];
values[poz] = values[indice];
values[indice] = aux;
v[values[indice]] = indice;
v[values[poz]] = poz;
pushUp(indice);
}
}
void pushDown(int poz) {
int indice;
if (rightSubtree(poz) == -1 && leftSubtree(poz) == -1)
return;
else if (rightSubtree(poz) == -1 && leftSubtree(poz) != -1)
indice = 2 * poz + 1;
else if (rightSubtree(poz) != -1 && leftSubtree(poz) == -1)
indice = 2 * poz + 2;
else {
if (values[rightSubtree(poz)] > values[leftSubtree(poz)])
indice = leftSubtree(poz);
else
indice = rightSubtree(poz);
}
if (values[poz] > values[indice]) {
T aux;
aux = values[poz];
values[poz] = values[indice];
values[indice] = aux;
pushDown(indice);
}
}
void insert(T x) {
if (dimVect < capVect) {
values[dimVect] = x;
v[x] = dimVect;
pushUp(dimVect);
dimVect++;
}
else
cout << "Heap-ul este plin!" << endl;
}
void remove (T x) {
dimVect--;
values[v[x]] = values[dimVect];
pushDown(v[x]);
}
T peek() {
return values[0];
}
T extractMin() {
dimVect--;
T min = values[0];
values[0] = values[dimVect];
pushDown(0);
return min;
}
};
int main() {
vector<int> numbers;
ifstream in;
in.open("heapuri.in");
ofstream out;
out.open("heapuri.out");
int n, i, Op, x;
in >> n;
Heap<int> heap(n);
for (i = 0; i < n; i++) {
in >> Op;
if (Op == 1) {
in >> x;
heap.insert(x);
numbers.push_back(x);
}
else if (Op == 2) {
in >> x;
heap.remove(numbers[x-1]);
}
else {
out << heap.peek() << "\n";
}
}
in.close();
out.close();
return 0;
}