As a games programmer, one of the basic tasks that everyone accomplishes is implementing A* Path Finding. First, let me say that path finding is not basic in video games, but the underlying concepts like A* can be. One way to improved the speed of A* Path Finding is to store the open list in a binary heap. Lucky for us there is already one in the standard library called priority queue. Upon further inspection I noticed some limitations of the priority queue.

There was no find() or contains() function to see if a node was already in the open list

There was no way to re-sort the list after invalidating it by changing the parent node of a node already on the open list

To fix this I implemented my own binary heap with these options available. They should be used sparingly because they are not fast operations for binary heaps, but I feel like they should still be available. Below is my code for the binary heap. Please note that I use C++11 features in this code so you will need a modern compiler like Clang 3.1.

#pragma once#include <functional>#include <vector>template<classT>classbheap{public:/** * Initialize the bheap with a function to compare the entries and an expected size to reduce allocations during insertion * * @param _compare A function to compare the entries. If compare(a,b) returns true, A is located higher up in the queue to be popped off first * @param expected_size The amount of space to allocate for values */bheap(std::function<bool(T&a,T&b)>_compare=[](T&a,T&b){returna<b;},size_texpected_size=100):compare(_compare){heap.reserve(expected_size);}/** * Initialize the bheap with a list of initial values, a function to compare the entries and an expected size to reduce allocations during insertion * * @param input An initializer list of values to be inserted into the heap * @param _compare A function to compare the entries. If compare(a,b) returns true, A is located higher up in the queue to be popped off first * @param expected_size The amount of space to allocate for values */bheap(conststd::initializer_list<T>&input,std::function<bool(T&a,T&b)>_compare=[](T&a,T&b){returna<b;},size_texpected_size=100):compare(_compare){heap.reserve((expected_size>input.size()?expected_size:input.size()));for(constT&val:input)heap.push_back(val);sort();}~bheap(){}/** * Check to see if the heap has no values * * * @return true if it has no values, otherwise false */boolempty()const{returnheap.empty();}/** * Get the size of the heap * * * @return The size of the heap */size_tsize()const{returnheap.size();}/** * Add a new value to the heap in the correct position * * @param value The new value to add */voidpush(constT&value){heap.push_back(value);percolate_up(heap.size()-1);}/** * Get the lowest value in the heap * * Gets the lowest value in the heap. This is determined by finding which value returns true compared against all other items when passed as the first parameter to the compare function. By defaul the compare function performs a simple operator<() * * * @return The lowest value in the heap */constT&top()const{returnheap[0];}/** * Remove the lowest value from the heap * */voidpop(){heap[0]=heap[heap.size()-1];heap.pop_back();percolate_down(0);}/** * Fully sort the heap assuming nothing about the current state. This operation is expensive so only call it if necessary. The pop and push functions will keep the heap sorted on their own. * */voidsort(){if(empty())return;for(size_ti=(heap.size()-1)/2;i!=-1;--i)percolate_down(i);}/** * Find the first entry that matches value. * * Find the first entry that matches value. If there are multiple entries with the same value there is no guarantee which one will be returned. Please note that if you change a value that affects the sorting then you must also make a call to sort() * * @param value The value to look for * * @return A pointer to the value in the heap matching the input value or nullptr if none is found */T*find(constT&value){for(T&val:heap)if(val==value)return&val;returnnullptr;}/** * Remove a value from the heap. * * Remove a value from the heap given a pointer to its location. This will call sort() automatically since the sorting of the heap will be destroyed. To remove by value, use find() * * @param value A pointer to the value in the heap that needs to be removed. */voidremove(constT*value){boolfound=false;for(autoit=heap.begin();it!=heap.end();++it){if(&*it==value){heap.erase(it);found=true;break;}}if(found)sort();}private:voidpercolate_down(size_ti){while(2*i+1<heap.size()){size_tleft_child=2*i+1;size_tright_child=2*i+2;size_tparent=(i-1)/2;size_tlast_leaf=heap.size()-1;size_tchild;if(right_child<heap.size()&&compare(heap[right_child],heap[left_child]))child=right_child;elsechild=left_child;if(compare(heap[child],heap[i])){//swapTtmp=heap[i];heap[i]=heap[child];heap[child]=tmp;i=child;}else{break;}}}voidpercolate_up(size_ti){size_tparent=(i-1)/2;while(parent<i){if(compare(heap[i],heap[parent])){Ttmp=heap[i];heap[i]=heap[parent];heap[parent]=tmp;i=parent;parent=(i-1)/2;}else{break;}}}std::function<bool(T&a,T&b)>compare;std::vector<T>heap;};