binary heap

[Rick]

Does anyone have a binary heap class or know where one is? I can't seem to find a "good" one.

[Canardia]

http://www.cplusplus.com/reference/stl/priority_queue/

[Rick]

Thanks Lum. I actually found one and here it is. I'm using this for my A* pathfinding with waypoints. It's supposed to make the A* algorithm much faster for a larger number of waypoints when used for the open list because you remove the need to search for the lowest f score because it'll always be the first element in the heap. You take a slight hit with insertion but it's still supposed to be much faster than using a normal array.

 

#pragma once
#include <vector>

using namespace std;

template <class Comparable>
class BinaryHeap
{
public:
explicit BinaryHeap( int capacity = 100 ) : array( capacity + 1 ), currentSize( 0 )
{
}

   bool isEmpty( ) const
{
	return currentSize == 0;
}
   bool isFull( ) const
{
	return currentSize == array.size( ) - 1;
}
   const Comparable & findMin( ) const
{
	//if( isEmpty( ) )
	//	throw Underflow( );
	return array[ 1 ];
}

   void insert( const Comparable & x )
{
	//if( isFull( ) )
	//	throw Overflow( );

	// Percolate up
	int hole = ++currentSize;
	for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
		array[ hole ] = array[ hole / 2 ];

	array[ hole ] = x;
}
   void deleteMin( )
{
	//if( isEmpty( ) )
	//	throw Underflow( );

	array[ 1 ] = array[ currentSize-- ];
       percolateDown( 1 );
}
   void deleteMin( Comparable & minItem )
{
	//if( isEmpty( ) )
       //        throw Underflow( );

	minItem = array[ 1 ];
       array[ 1 ] = array[ currentSize-- ];
       percolateDown( 1 );
}
   void makeEmpty( )
{
	currentSize = 0;
   }

private:
int					currentSize;// Number of elements in heap
   vector<Comparable>	array;        // The heap array

   void buildHeap( )
{
	for( int i = currentSize / 2; i > 0; i-- )
		percolateDown( i );
   }
   void percolateDown( int hole )
{
/* 1*/      int child;
/* 2*/      Comparable tmp = array[ hole ];

/* 3*/      for( ; hole * 2 <= currentSize; hole = child )
           {
/* 4*/          child = hole * 2;
/* 5*/          if( child != currentSize && array[ child + 1 ] < array[ child ] )
/* 6*/              child++;
/* 7*/          if( array[ child ] < tmp )
/* 8*/              array[ hole ] = array[ child ];
               else
/* 9*/              break;
           }
/*10*/      array[ hole ] = tmp;
   }
};

 

Usage:

#include "BinaryHeap.h"

int main()
{
BinaryHeap<int> heap(100);

heap.insert(5);
heap.insert(8);
heap.insert(15);
heap.insert(3);

int a = 0;

// delete min and return it to parameter. this returns 3
heap.deleteMin(a);

// find the min. this returns 5 now because 3 was removed
int b = heap.findMin();

return 0;
}

[Pixel Perfect]

It's supposed to make the A* algorithm much faster for a larger number of waypoints when used for the open list because you remove the need to search for the lowest f score because it'll always be the first element in the heap.

I use a binary heap in mine and the performance certainly seems pretty good!