myMaxheap.cpp

Go to the documentation of this file.

#include "myMaxheap.h"


myMaxheap::myMaxheap(void)
{
    mytuple *newtuple;
    heaplimit = 1;                          // first free location is A[1]
    arraysize = heapmin+1;                  // 
    isempty   = true;                       // heap is initially empty
    A = new hnode [arraysize];              // allocate array for heap
    for (int i=0; i<arraysize; i++) {           // initialize heap values
        newtuple = new mytuple;             // 
        A[i].d = newtuple;                  // 
        A[i].d->m = -4294967296.0;          // a very negative value; unlikely to be a valid dQ
        A[i].d->i = 0;                      // 
        A[i].d->j = 0;                      // 
        A[i].d->k = i;                      // 
    }
}
myMaxheap::myMaxheap(int size) {
    mytuple *newtuple;
    heaplimit = 1;                          // first free location is A[1]
    arraysize = size+1;                     // 
    isempty   = true;                       // heap is initially empty
    A = new hnode [arraysize];              // allocate array for heap
    for (int i=0; i<arraysize; i++) {           // initialize heap values
        newtuple = new mytuple;             // 
        A[i].d = newtuple;                  // 
        A[i].d->m = -4294967296.0;          // a very negative value; unlikely to be a valid dQ
        A[i].d->i = 0;                      // 
        A[i].d->j = 0;                      // 
        A[i].d->k = i;                      // 
    }
}

myMaxheap::~myMaxheap(void)
{
    for (int i=0; i<arraysize; i++) { delete A[i].d; }  // first delete the containers pointed to
        delete [] A;    
}

// Pop Maximum ------------------------------------------------------------------------
mytuple myMaxheap::popMaximum() {               // O(log k) time
    mytuple temp = returnMaximum();
    deleteItem(A[1].d);
    return temp;
}

// Return Maximum --------------------------------------------------------------------
mytuple myMaxheap::returnMaximum() {            // O(1) time
    mytuple temp;
    temp.m = A[1].d->m;                 // 
    temp.i = A[1].d->i;                 // 
    temp.j = A[1].d->j;                 // 
    temp.k = A[1].d->k;                 // grab A's data
    return temp;
}
int myMaxheap::returnArraysize() { return arraysize; } 
int myMaxheap::returnHeaplimit() { return heaplimit; }


// Heapification functions ------------------------------------------------------------
int myMaxheap::downsift(int index) {            // O(log k) time
    bool stopFlag  = false;
    int L       = left(index);
    int R       = right(index);
    int swap;
    mytuple* temp;
    
    while (!stopFlag) {
        // check that both children are within the array boundaries
        if ((L < heaplimit) && (R < heaplimit)) {
            if (A[L].d->m > A[R].d->m) { swap = L; } else { swap = R; } // first choose larger of the children
        } else { if (L < heaplimit) { swap = L; } else { break; } }     // only one child to consider
        
        // now decide if need to exchange A[index] with A[swap]
        if (A[index].d->m < A[swap].d->m) {
            temp          = A[index].d;   // exchange pointers A[index] and A[swap]
            A[index].d    = A[swap].d;    // 
            A[index].d->k = index;      // note A[index].d's change of array location
            A[swap].d     = temp;       // 
            A[swap].d->k  = swap;       // note A[swap].d's change in array location
            
            index = swap;               // update indices for next pass
            L     = left(index);        // 
            R     = right(index);       //          
        } else { stopFlag = true; }
    }
    return index;                       // return the new index location of downsifted element
}
int myMaxheap::upsift(int index) {          // O(log k) time
    bool stopFlag = false;
    int P         = parent(index);
    mytuple* temp;
    while (!stopFlag) {
        // decide if A[index] needs to move up in tree
        if ((P > 0) && (A[index].d->m > A[P].d->m)) {
            temp          = A[index].d;   // exchange A[index] and A[P]
            A[index].d    = A[P].d;     // 
            A[index].d->k = index;      // note A[index].d's change of array location
            A[P].d        = temp;       // 
            A[P].d->k     = P;          // note A[P].d's change of array location
            
            index = P;              // update indices for next pass
            P     = parent(index);      // 
        } else { stopFlag = true; }
    }
    return index;
}

int  myMaxheap::left  (int index) { return 2*index;     }
int  myMaxheap::right (int index) { return 2*index+1;    }
int  myMaxheap::parent(int index) { return (int)index/2; }

void myMaxheap::grow() {                                // O(k) time
    mytuple *newtuple;
    hnode   *B;                                 // scratch space for expansion of A
    B = new hnode [arraysize];                      // 
    for (int i=0; i<arraysize; i++) { B[i].d = A[i].d; }   // copy A into B
    delete [] A;                                    // delete old array of addresses
    A = new hnode [2*arraysize];                        // grow A by factor of 2
    for (int i=0; i<arraysize; i++) { A[i].d = B[i].d; }   // copy B into first half of A
    for (int i=arraysize; i<(2*arraysize); i++) {       // initialize new heap values
        newtuple  = new mytuple;                        // 
        A[i].d    = newtuple;                       // 
        A[i].d->m = -4294967296.0;                  // 
        A[i].d->i = 0;                              // 
        A[i].d->j = 0;                              // 
        A[i].d->k = i;                              // 
    }                                        
    delete [] B;                                    // delete scratch space B
    arraysize = 2*arraysize;                            // update size of array
    return;
}
void myMaxheap::shrink() {                              // O(k) time
    mytuple *newtuple;
    hnode   *B;                                 // scratch space for contraction of A
    B = new hnode [heaplimit];                      // 
    for (int i=0; i<heaplimit; i++) { B[i].d = A[i].d; }   // copy A into B
    delete [] A;                                    // delete old array of addresses
    A = new hnode [arraysize/2];                        // shrink A by factor of 2
    for (int i=0; i<heaplimit; i++) { A[i].d = B[i].d; }   // copy B into A
    for (int i=heaplimit; i<(arraysize/2); i++) {       // initialize new heap values
        newtuple  = new mytuple;                        // 
        A[i].d    = newtuple;                       // 
        A[i].d->m = -4294967296.0;                  // 
        A[i].d->i = 0;                              // 
        A[i].d->j = 0;                              // 
        A[i].d->k = i;                              // 
    }                                        
    delete [] B;                                    // delete scratch space B
    arraysize = arraysize/2;                            // update size of array
    return;
}

// Insert + Update Functions --------------------------------------------------------------
mytuple* myMaxheap::insertItem(const mytuple newData) {         // O(log k) time
    int index;
    mytuple *pointer;
    if (heaplimit >= (arraysize-1)) { grow(); }  // if heap is full, grow by factor of 2

    index       = heaplimit;            // 
    A[index].d->m  = newData.m;         // copy newData onto the bottom of the heap
    A[index].d->i  = newData.i;         // 
    A[index].d->j  = newData.j;         // 
    A[index].d->k  = index;             //
    pointer     = A[index].d;           // store pointer to container
    heaplimit++;                        // note the larger heap
    upsift(index);                      // upsift new item up to proper spot
    if  (heaplimit > 1) { isempty = false; }
    
    return pointer;
}

void myMaxheap::updateItem(mytuple *address, mytuple newData) {   // O(log k) time
    double oldm = address->m;
    address->m = newData.m;                     //   udpate the dQ stored
    address->j = newData.j;                     //   udpate the community to which to join
    if (oldm > newData.m) { downsift(address->k); }   //   downsift if old value was larger
    else                  { upsift(address->k);   }   //   upsift otherwise
    return;
}
void myMaxheap::updateItem(mytuple *address, double newStored) {    // O(log k) time
    double oldm    = address->m;
    address->m  = newStored;                        // udpate the dQ stored
    if (oldm > newStored) { downsift(address->k); }     // downsift if old value was larger
    else                  { upsift(address->k);   }     // upsift otherwise
    return;
}
void myMaxheap::deleteItem(mytuple *address) {
    mytuple *swap;
    int smal = heaplimit-1;
    int index = address->k;

    if (heaplimit==2) {                     // check if deleting last item in heap
        A[1].d->m       = -4294967296.0;        // zero out root data
        A[1].d->i       = 0;                    // 
        A[1].d->j       = 0;                    // 
        A[1].d->k       = 1;                    // 
        isempty     = true;             // note the heap's emptiness
        heaplimit--;                        // decrement size of heap to empty
    } else {
        A[index].d->m  = -4294967296.0;     // zero out the deleted item's data
        A[index].d->i   = 0;                    // 
        A[index].d->j  = 0;                 // 
        swap            = A[index].d;           // swap this element with item at end of heap
        A[index].d  = A[smal].d;            // 
        A[smal].d   = swap;             // 
        A[index].d->k  = index;             // note the change in locations
        A[smal].d->k  = smal;               // 
        heaplimit--;                        // note change in heap size
        downsift(index);                    // downsift moved element to new location; O(log k)
        if ((heaplimit/2 > heapmin) && (heaplimit == (arraysize/2))) { shrink(); } // shrink by factor of 2 if necessary
    }
    return;
}
bool myMaxheap::heapIsEmpty() { return isempty; }
int  myMaxheap::heapSize()    { return heaplimit-1; }

// Display Functions --------------------------------------------------------------------
void myMaxheap::printHeap() {
    for (int i=1; i<heaplimit; i++) {
        std::cout << A[i].d <<"\t["<<A[i].d->k<<"]\tdQ = "<<A[i].d->m<<"\t"<<A[i].d->i<<" -> "<<A[i].d->j<<"\n"; }
    return;
}
void myMaxheap::printHeapTop10() {
    int limit;
    if (heaplimit>10) { limit = 11; } else { limit = heaplimit; }
    for (int i=1; i<limit; i++) {
        std::cout << A[i].d <<"\t["<<A[i].d->k<<"]\tdQ = "<<A[i].d->m<<"\t"<<A[i].d->i<<" -> "<<A[i].d->j<<"\n"; }
    return;
}

// ------------------------------------------------------------------------------------