gistfile1.cpp

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

#include <iostream>
#include <vector>
using namespace std;


class LDHeap {
public:
    vector<int> heapVec;
    
    int parent(int i){
        return i/2;
    }
    
    int left(int i) {
        return 2*i;
    }
    
    int right(int i) {
        return 2*i + 1;
    }
    
    void buildHeap(vector<int> & vec){
        for (int i = vec.size()/2; i>=1; i--) {
            hepify(vec, i);
        }
    }
    
private:
    void LDSpaw(int & a,int & b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
    
    void hepify(vector<int> & vec,int i) {
        int l = left(i),r = right(i);
        static int largest = 0;
        if(l <= vec.size() && vec[l] > vec[i]){
            largest = l;
        } else {
            largest = i;
        }
        if (r <= vec.size() && vec[r] > vec[largest]){
            largest = r;
        }
        if (largest  !=  i) {
            LDSpaw(vec[i], vec[largest]);
            hepify(vec, largest);
        }
    }
};


int main(int argc, const char * argv[])
{
    cout<<"start"<<endl;
    LDHeap ldheap;
    ldheap.heapVec.push_back(INT_MIN);
    for (int i = 0; i < 10; i++) {
        int val = 0;
        cin>>val;
        ldheap.heapVec.push_back(val);
    }
    ldheap.buildHeap(ldheap.heapVec);
    for (int i = 0; i < 11; i++) {
        cout<<ldheap.heapVec[i]<<" ";
    }
    cout<<endl;
    
    return 0;
}