Rick Posted September 20, 2010 Share Posted September 20, 2010 Does anyone have a binary heap class or know where one is? I can't seem to find a "good" one. Quote Link to comment Share on other sites More sharing options...
Canardia Posted September 20, 2010 Share Posted September 20, 2010 http://www.cplusplus.com/reference/stl/priority_queue/ Quote ■ Ryzen 9 ■ RX 6800M ■ 16GB ■ XF8 ■ Windows 11 ■ ■ Ultra ■ LE 2.5 ■ 3DWS 5.6 ■ Reaper ■ C/C++ ■ C# ■ Fortran 2008 ■ Story ■ ■ Homepage: https://canardia.com ■ Link to comment Share on other sites More sharing options...
Rick Posted September 20, 2010 Author Share Posted September 20, 2010 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; } Quote Link to comment Share on other sites More sharing options...
Pixel Perfect Posted September 20, 2010 Share Posted September 20, 2010 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! Quote Intel Core i5 2.66 GHz, Asus P7P55D, 8Gb DDR3 RAM, GTX460 1Gb DDR5, Windows 7 (x64), LE Editor, GMax, 3DWS, UU3D Pro, Texture Maker Pro, Shader Map Pro. Development language: C/C++ Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.