Cod sursa(job #1974530)

Utilizator RathebaSerbanescu Andrei Victor Ratheba Data 27 aprilie 2017 22:34:35
Problema Heapuri Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>

using namespace std;

const int MAX = 200005;

ifstream fin ("heapuri.in");
ofstream fout ("heapuri.out");


void insertHeap(int valIndex);
void delHeap(int chronPos);
void printHeap();
void swapHeap();
void goUp(int node);
void goDown(int node);


int heap[MAX];
int vpoz[MAX];
int vals[MAX];
int hLastIndex;


int main()
{
    int n, command, value, chronPos;
    int valIndex = 0;
    hLastIndex = 1;

    fin >> n;
    for(int i = 1; i <= n; i++) {
        fin >> command;
        if(command == 1) {
            fin >> value;
            vals[++valIndex] = value;
            insertHeap(valIndex);

        } else if(command == 2) {
            fin >> chronPos;
            delHeap(chronPos);

        } else {
            printHeap();
        }
    }
    return 0;
}
void swapHeap(int node1, int node2)
{
    int aux;
    aux = heap[node1];
    heap[node1] = heap[node2];
    heap[node2] = aux;

    vpoz[heap[node1]] = node1;
    vpoz[heap[node2]] = node2;
}

void insertHeap(int valIndex)
{
    heap[hLastIndex] = valIndex;
    vpoz[valIndex] = hLastIndex;


    hLastIndex++;
    goUp(hLastIndex - 1);
}

void goUp(int node)
{
    int father = node / 2;

    if(node == 1) {
        return;
    }
    if(vals[heap[node]] < vals[heap[father]]) {
        swapHeap(father, node);
        goUp(father);
    }
}
void delHeap(int chronPos)
{
    int node = vpoz[chronPos];

    swapHeap(node, hLastIndex - 1);
    hLastIndex--;

    goDown(node);
}
void printHeap()
{
    fout << vals[heap[1]] << '\n';
}
void goDown(int node)
{
    int child = node * 2;
    if(child >= hLastIndex) {
        return;
    }
    if(child + 1 < hLastIndex
       && vals[heap[child]] > vals[heap[child + 1]]) {
        child++;
    }

    if(vals[heap[node]] > vals[heap[child]]) {
        swapHeap(node, child);
        goDown(child);
    }
}