Friday, January 13, 2017

Implement heap using vector STL c++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void heapify(vector<int> &v, int t) {
    int s = v.size();
    if ( ((s> 2*t+1 ) && (v[t] > v[2*t+1])) || ((s>2*t+2) && (v[t] > v[2*t+2]))) {
        if (s>2*t+2) {
           
            int index = v[2*t+1] > v[2*t+2] ? 2*t+2 : 2*t+1;
            int temp = v[index];
            v[index] = v[t];
            v[t] = temp;
            heapify(v, index);
        } else {           
           
            int temp = v[2*t+1];
            v[2*t+1] = v[t];
            v[t] = temp;
            heapify(v, 2*t+1);
        }
    }
}

void insert_h(vector<int> &v, int t) {
   
    if (v.size() > 0) {
        v.push_back(t);
        t= v.size() -1;
        while((t-1)/2>= 0 && v[t] < v[((t-1)/2)]) {
            int temp = v[t];
            v[t] = v[(t-1)/2];
            v[(t-1)/2] = temp;
            t = (t-1)/2;
        }
    } else {
        v.push_back(t);
    }
}

void delete_h (vector<int> &v , int t) {
    for (int i = 0; i< v.size(); i++) {
        if (v[i] == t) {
            v[i] = v.back();
            v.pop_back();
            heapify(v, i);
            break;
        }
    }
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    vector<int> v;
    int n;
    int q;
    int t;
    cin>>n;
    for (int i =0; i<n; i++) {
        cin>>q;
        if (q == 1) {
            cin>>t;
            insert_h(v,t);
        } else if (q == 2) {
            cin>>t;
            delete_h(v,t);
        } else {
            cout<<v[0]<<endl;
        }
    }
    return 0;

No comments:

Post a Comment