comparing structs using Comparable class!!!

[abhishek2301]

Hello,
I have a BinaryHeap class that uses template <class Comparable> as follows:

template <class Comparable>
class BinaryHeap {
public:
    explicit BinaryHeap (int capacity = 0)
    const Comparable & findMin( ) const;
    .........................................................
private:
    int currentSize;
    vector<Comparable> array;
    ........................................................
};

template <class Comparable>
const Comparable & BinaryHeap<Comparable>::findMin( ) const
{
if( isEmpty( ) )
    throw Underflow( );
 return array[ 1 ];
}
..............................................................
}

This is the BinaryHeap class from Weiss book on Data Structure.
Now, I want to create the above BinaryHeap with a struct(a). 'a' have 2 fields: a.val(double) and a.g(int). I want the heap to be ordered by a.val or the key value by which the heap to be created is a.val and also all the heap operations should be based on a.val
How can I do this???

Your help is highly appreciated!!!
Thanks!!!

[Ancient Dragon]

>>explicit BinaryHeap (int capacity = 0)
capacity a pretty useless variable! It goes out of scope and is destroyed immediately.

[Murtan]

You're not showing any of the actual compares. The structs to be compared will need to have implemented whatever operator or method is called to do the compares.

Note that the word 'Comparable' in your template definition makes no constraint on the type of things you can put on your list. It is just the name by which you know the class inside the template.

For most of these ordered collection objects, I prefer to give the collection a pointer to a comparison function that will make the actual compare between two objects, rather than an operator or named method call. The primary reason I have is that I might want the collection ordered by different fields at different times.

As an example of multi-sorting, if you had Customer (struct/class) that contained the customer_id, first_name, last_name, address, city, state, zip. You might want the collection ordered by customer_id when relating by that field, ordered by last_name and first_name when building a customer directory, and ordered by zip when producing the mailing labels.

If the collection is ordered using operator <(...) the collection can only have one order...ever.

[abhishek2301]

Hello,
This is the implementation of the BinaryHeap.

#include "BinaryHeap.h"

// Construct the binary heap.
template <class Comparable>
BinaryHeap<Comparable>::BinaryHeap( )
  : array( 11 ), theSize( 0 )
{
}

// Construct the binary heap.
// v is a vector containing the initial items.
template <class Comparable>
BinaryHeap<Comparable>::BinaryHeap( const vector<Comparable> & v )
  : array( v.size( ) + 1 ), theSize( v.size( ) )
{
    for( int i = 0; i < v.size( ); i++ )
        array[ i + 1 ] = v[ i ];
    buildHeap( );
}

// Insert item x into the priority queue, maintaining heap order.
// Duplicates are allowed.
template <class Comparable>
void BinaryHeap<Comparable>::insert( const Comparable & x )
{
    array[ 0 ] = x;   // initialize sentinel
    if( theSize + 1 == array.size( ) )
        array.resize( array.size( ) * 2 + 1 );

      // Percolate up
    int hole = ++theSize;
    for( ; x < array[ hole / 2 ]; hole /= 2 )
        array[ hole ] = array[ hole / 2 ];
    array[ hole ] = x;
}

// Find the smallest item in the priority queue.
// Return the smallest item, or throw UnderflowException if empty.
template <class Comparable>
const Comparable & BinaryHeap<Comparable>::findMin( ) const
{
    if( isEmpty( ) )
        throw UnderflowException( );
    return array[ 1 ];
}

// Remove the smallest item from the priority queue.
// Throw UnderflowException if empty.
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( )
{
    if( isEmpty( ) )
        throw UnderflowException( );

    array[ 1 ] = array[ theSize-- ];
    percolateDown( 1 );
}

// Remove the smallest item from the priority queue
// and place it in minItem. Throw UnderflowException if empty.
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( Comparable & minItem )
{
    minItem = findMin( );
    array[ 1 ] = array[ theSize-- ];
    percolateDown( 1 );
}

// Establish heap-order property from an arbitrary
// arrangement of items. Runs in linear time.
template <class Comparable>
void BinaryHeap<Comparable>::buildHeap( )
{
    for( int i = theSize / 2; i > 0; i-- )
        percolateDown( i );
}

// Test if the priority queue is logically empty.
// Return true if empty, false otherwise.
template <class Comparable>
bool BinaryHeap<Comparable>::isEmpty( ) const
{
    return theSize == 0;
}

// Make the priority queue logically empty.
template <class Comparable>
void BinaryHeap<Comparable>::makeEmpty( )
{
    theSize = 0;
}

// Internal method to percolate down in the heap.
// hole is the index at which the percolate begins.
template <class Comparable>
void BinaryHeap<Comparable>::percolateDown( int hole )
{
    int child;
    Comparable tmp = array[ hole ];

    for( ; hole * 2 <= theSize; hole = child )
    {
        child = hole * 2;
        if( child != theSize && array[ child + 1 ] < array[ child ] )
            child++;
        if( array[ child ] < tmp )
            array[ hole ] = array[ child ];
        else
            break;
    }
    array[ hole ] = tmp;
}

Where do I need to implement the operators for the Comparable class so that I can compare the structs with a.val
I need to order the heap by a.val(struct 'a' with filed 'val') always and I do not need to comapre them with any other fields.

Thanks!!!

[Murtan]

This code array[ child + 1 ] < array[ child ] from percolateDown uses operator < to make the comparison. So your objects need to implement opertor <.

In your case, you wanted to compare the 'val'

bool operator <(struct a const & x, struct a const & y)
{
    return x.val < y.val;
}

This works ok for structs as their members are all public (well, by default anyway). If the data items 'val' were not publically accessable, you could either declare the operator as part of the struct (not usually necessary) or use an accessor. (i.e. getVal())

[abhishek2301]

Thanks for the input.
Now I want to implement all the other compare methods such as > = etc.
How do I do this???

Thanks!!!

[Murtan]

That's pretty easy to derive from the above example, why don't you try what you think should work.

If you try something and it doesn't work, post what you tried here along with the observed results and we'll help you work on it.

if you post more code, please use c++ code tags [code=c++] [/code] around your code.