CSCI 340 assign 7

#include <cstdlib>
#include <iomanip>
#include <vector>
#include <iostream>
#include <algorithm>
//Terina BUrr
//Assignment 7
//Due 11/06/15
//Section 1

using namespace std;
int NO_ITEMS = 10;
int ITEM_W=4;

void build_heap ( vector < int >& v, int heap_size, bool (*compar)(int, int) );
void heapify( vector < int >& v, int heap_size, int r, bool (*compar)(int, int) );
bool less_than ( int e1, int e2 );
bool greater_than ( int e1, int e2 );
void heap_sort ( vector < int >& v, int heap_size, bool (*compar)(int, int) );
int extract_heap ( vector < int >& v, int& heap_size, bool (*compar)(int, int) );
void print_vector ( vector < int >& v, int pos, int size );
/***************************************************************
Function: build heap

Use:      It builds the heap by invoking heapify

Arguments:  1. &v: reference to a vector that you make the heap out of
        2. heap_size:  the size of the heap
        3. compar: pointer to a function accepting two int arguments and returning an integer

Returns:   nothing
***************************************************************/

void build_heap ( vector < int >& v, int heap_size,bool (*compar)(int x, int y) )
{
    for(int i = heap_size/2; i>= 0; i--)
    {
        heapify(v, heap_size, i , compar);
    }

}
/***************************************************************
Function: heapify

Use:      specifies the size of the whole heap contained by the vector uses function compar to compare two functions

Arguments:  1. &v: reference to a vector
        2. heap_size:  the size of the heap
        3. compar: pointer to a function accepting two int arguments and returning an integer
        4. r where the function heapifies what position
Returns:   nothing
***************************************************************/

void heapify( vector < int >& v, int heap_size, int r, bool (*compar)(int x, int y) )
{
    int min = r;
    if( 2*r<=heap_size && compar(v[2*r],v[r]) )
        min = 2*r;
    if(2*r+1<= heap_size&&compar(v[2*r+1],v[min]))
        min = 2* r +1;
    if (min!=r)
    {
        int temp = v[r];
        v[r] = v[min];
        v[min] = temp;
        heapify(v,heap_size, min,compar );
    }
}
/****************
Function: less than

Use:      sees if e1 is less than e2

Arguments:  1. E1: int that e2 is compared to
        2. e2: int that e1 is compared to

Returns:   true or false if e1 is less than e2
***************************************************************/

bool less_than ( int e1, int e2 )
{
    if(e1<e2)
        return true;
    else
        return false;
}
/***************************************************************
Function: greater than

Use:      sees if e1 is greater than e2

Arguments:  1. E1: int that e2 is compared to
        2. e2: int that e1 is compared to

Returns:   true or false if e1 is greater than e2
***************************************************************/

bool greater_than ( int e1, int e2 ){
    if(e1>e2)
        return true;
    else
        return false;
}
/***************************************************************
Function: heap_sort

Use:      it sorts the heap

Arguments:  1. &v: reference to a vector
        2. heap_size:  the size of the heap
        3. compar: pointer to a function accepting two int arguments and returning an integer

Returns:   nothing
***************************************************************/

void heap_sort ( vector < int >& v, int heap_size, bool (*compar)(int, int) )
{
//                extract_heap(v,heap_size,compar);
    for(unsigned int i = 0 ; i < v.size() ; ++i) //going through the vector
    {
    int temp = i+1;
    while(temp != 1 && compar(v[temp/2-1],v[temp-1]))
    {
        std::swap(v[temp-1],v[temp/2-1]);//swap values if
        temp /= 2;//make temp = temp/2
    }
    }
    //sorting the heap
    for(int i = v.size() ; i > 1 ; --i)
    {
    std::swap(v[0],v[i-1]);
    if(v[i] == 1000000) // -10000)
    v[i] =   extract_heap(v,heap_size,compar);//need to extract the heap but wasnt sure where to put it


    int temp = 1;
    while( (temp*2   < i && compar(v[temp-1],v[temp*2-1])  ) ||
           (temp*2+1 < i && compar(v[temp-1],v[temp*2]))  )
    {
        int temp2;
        if(temp*2+1 < i && compar(v[temp*2-1],v[temp*2]))
        {
        temp2 = temp*2+1;
        }
         else
        {
        temp2 = temp*2;
        }
        std::swap(v[temp-1],v[temp2-1]);

     temp = temp2;
    }
    }

}
/***************************************************************
Function: extract heap

Use:      it extracts the root of the tree and replaces it with the last value and returns the last value

Arguments:  1. &v: reference to a vector
        2. heap_size:  the size of the heap
        3. compar: pointer to a function accepting two int arguments and returning an integer

Returns:   the old root
***************************************************************/

int extract_heap ( vector < int >& v, int& heap_size, bool(*compar)(int, int) )
{
    int root = v[1];
    int temp = root;
    int last = v[heap_size-1];
    root = last;
    v[1] = last;
    heapify(v,heap_size,v[0],compar);
 //is suppose to extract the root and put it where the last element is
    return temp;
}
/***************************************************************
Function: print vector

Use:      prints vector

Arguments:  1. &v: reference to a vector
        2. size:  the size of the vector
        3. pos: position where you start

Returns:   nothing
***************************************************************/


void print_vector ( vector < int >& v, int pos, int size )
{
    vector<int>::iterator iter;
    int count =0;
    iter = v.begin()+pos;
    while(iter !=v.end())
    {
        count++;
        cout << setw(ITEM_W) << *iter;
//prints the numbers at a width that is four spaces apart
            if(count % NO_ITEMS == 0)
            {
                cout <<endl;
            }
//if there is more than 10 numbers on a line then they start a new line
        iter++;
    }
cout<<endl;

}




int main(int argc, char** argv) {
    // ------- creating input vector --------------
    vector<int> v;
    v.push_back(-1000000);    // first element is fake
    int heap_size = 24;
    for (int i=1; i<=heap_size; i++)
        v.push_back( i );
    random_shuffle( v.begin()+1, v.begin()+heap_size+1 );
    cout << "\nCurrent input numbers: " << endl;
    print_vector( v, 1, heap_size );

    // ------- testing min heap ------------------
    cout << "\nBuilding a min heap..." << endl;
    build_heap(v, heap_size, less_than);
    cout << "Min heap: " << endl;
    print_vector( v, 1, heap_size );
    heap_sort( v, heap_size, less_than);
    cout << "Heap sort result (in ascending order): " << endl;
    print_vector( v, 1, heap_size );

    // ------- testing max heap ------------------
    cout << "\nBuilding a max heap..." << endl;
    build_heap(v, heap_size, greater_than);
    cout << "Max heap: " << endl;
    print_vector( v, 1, heap_size );
    heap_sort( v, heap_size, greater_than);
    cout << "Heap sort result (in descending order): " << endl;
    print_vector( v, 1, heap_size );

    return 0;
}