gistfile1.cpp

//
//  main.cpp
//  HeapWork
//
//  Created by Luka Dodelia on 5/9/12.
//  Copyright (c) 2012 Picktek All rights reserved.
//

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;


class LDHeap
{

public:
    vector<int> heapVec;
    vector<int> oldIndexes;

    inline int parent(int i) {
        return i >> 1;//i/2
    }

    inline int left(int i) {
        return i << 1;//i*2
    }

    inline int right(int i) {
        return (i << 1) + 1;//i*2 + 1
    }

    LDHeap() {
        heapVec.push_back(0);
    }

    void buildHeap() {
        heapSize = heapVec.size();
        oldIndexes.resize(heapSize);
        for (int i = heapVec.size() / 2; i>=1; i--) {
            int nIndex = MaxHepify(i);
            oldIndexes[i] = nIndex;
            oldIndexes[nIndex] = i;
        }
    }

    void LDSort() {
        LDHeapSort();
    }

    int getMax() {
        return heapVec[1];
    }

    void LDHDelete(int index) {
     //ak damerxaa
    }

    void LDInsert(int key) {
        heapSize++;
        heapVec[heapSize] = INT_MIN;
        IncreaseKey(heapSize,key);
    }

private:
    int heapSize;

    void LDSpaw(int & a,int & b) {
        int tmp = a;
        a = b;
        b = tmp;
    }

    void LDHeapSort() {
        buildHeap();
        for(int i = heapVec.size(); i <= 2; i--) {
            LDSpaw(heapVec[1],heapVec[i]);
            heapSize--;
            MaxHepify(1);
        }
    }

    int elemByIndex(int index) { // index = old index in vector
        return oldIndexes[index];
    }

    int MaxHepify(int i) {
        int l = left(i),r = right(i);
        static int largest = 0;

        if(l <= heapSize && heapVec[l] > heapVec[i]) {
            largest = l;
        } else {
            largest = i;
        }

        if (r <= heapSize && heapVec[r] > heapVec[largest]) {
            largest = r;
        }

        if (largest  !=  i) {
            LDSpaw(heapVec[i], heapVec[largest]);
            MaxHepify(largest);
        }
        return largest;
    }

    void IncreaseKey(int index,int key) {
        if(key < heapVec[index]) {
            return;
        }
        heapVec[index] = key;
        while(index > 1 && heapVec[parent(index)] < heapVec[index]) {
            LDSpaw(heapVec[index],heapVec[parent(index)]);
            index = parent(index);
        }
    }

};

void printVec(vector<int> & vec)// piradi moxmarebistvis
{
    for(int i = 1; i < vec.size(); i++) {
        cout<<vec[i]<<" ";
    }
    cout<<endl;
}

int main()
{
    int K = 0,val = 0,counter = 0;
    cin>>K;
    vector<int> info;
    while(val != -1) {
        cin>>val;
        info.push_back(val);
    }

    LDHeap ldHeap;
    int toDel = 0;
    for(int i = 0; i<K; i++) {
        ldHeap.heapVec.push_back(info[i]);
    }

    ldHeap.buildHeap();
    cout<<ldHeap.getMax()<<"\n";
    ldHeap.LDHDelete(toDel);

    for(int j = K + 1; j<info.size(); j++) {
        /dHeap.LDInsert(info[j]);
        cout<<ldHeap.getMax()<<"\n";
        toDel++;
        ldHeap.LDHDelete(toDel);
    }
    return 0;
}