myMaxheap.h

Go to the documentation of this file.

#pragma once
#if !defined(TUP_INCLUDED)
#define TUP_INCLUDED
struct mytuple {
    double    m;                    // stored value
    int     i;                  // row index
    int     j;                  // column index
    int     k;                  // heap index
};
#endif

#if !defined(MAXHEAP_INCLUDED)
#define MAXHEAP_INCLUDED

#include <iostream>

/*   Because using this heap requires us to be able to modify an arbitrary element's
    data in constant O(1) time, I use to tricky tactic of having elements in an array-
    based heap only contain addresses to the data, rather than the data itself. In this
    manner, an external program may freely modify an element of the heap, given that it
    possesses a pointer to said element (in an array-based heap, the addresses and the 
    value in that address are not bound and thus may change during the heapify() operation).
*/
struct hnode 
{ 
    mytuple     *d; 
};
const int heapmin = 3;
//const double tiny = -4294967296.0;


class myMaxheap
{
private:
    hnode    *A;                    
    int       heaplimit;            
    int     arraysize;              
    bool        isempty;            

    int     downsift(int i);        
    int     upsift  (int i);        
    int     left    (int i);        
    int     right   (int i);        
    int     parent  (int i);        
    void        grow();             
    void        shrink();           
  
public:
    myMaxheap(void);                    // default constructor
    myMaxheap(int size);                
    ~myMaxheap(void);                   // default destructor
    
    int     heapSize();                                         
    bool        heapIsEmpty();                                  
    mytuple *insertItem(const mytuple newData);                 
    mytuple popMaximum();                                       
    mytuple returnMaximum();                                    
    void        printHeap();                                    
    void        printHeapTop10();                               
    void        updateItem(mytuple *address, mytuple newData);  
    void        updateItem(mytuple *address, double newStored); 
    void        deleteItem(mytuple *address);                   
    int     returnArraysize();                                  
    int     returnHeaplimit();                                  
    
};

#endif