This is a header-only implementation of rank-pairing heaps (rp-heap) written in C++11. The idea of rp-heap is based on lazy binomial queue with the rank restriction to ensure the balance of half trees. Heap has wide applications like heapsort, k-smallest elements, Prim's algorithm and notably well-known Dijkstra's shortest-path algorithm. We are implementing this data structure because:
- std::priority_queue does not support decrease-key
- Fibonacci heap is theoretically fast but not good in practice
- we are looking for an efficient 'decrease key' operation in pathfinding algorithm which is better than practical d-ary heap and pairing heap
In game development, A* algorithm is a standard shortest path algorithm. You can download this repository to build the solution and run the demo of A* pathfinding using rp-heap in MSVC.
The implementation mimics STL containers and provides STL-like member functions. To use it, simply include the header file rank_pairing_heaps/astarheap/rp_heap.h
// make heap
rp_heap(const _Pr& _Pred = _Pr());
// capacity
bool empty() const;
size_type size() const;
// find-min
const_reference top() const;
// insert
const_iterator push(const value_type& _Val);
const_iterator push(value_type&& x);
// delete-min
void pop();
void pop(value_type& _Val);
// delete-all
void clear();
// decrease-key
void decrease(const_iterator _It, const value_type& _Val);
// for type 1 rank reduction (default type 2)
#define TYPE1_RANK_REDUCTION
#include <iostream>
#include <algorithm> // std::random_shuffle
#include "rp_heap.h"
#include <vector>
int main()
{
std::vector<int> v;
int size = 1000;
for (int i = 0; i < size; i++)
v.push_back(i + 1); // v = {1, 2,... 1000}
std::random_shuffle(v.begin(), v.end()); // shuffle v
rp_heap<int> heap;
std::vector<rp_heap<int>::const_iterator> its; // save the iterators returned from push
for (int i = 0; i < size; i++)
its.push_back(heap.push(v[i]));
heap.decrease(its[0], 0); // a number decreases to 0
heap.pop(); // pop that number
for (int i = 1; i < size; i++)
heap.decrease(its[i], *its[i] - 1); // each element in heap is decreasd by 1
while (!heap.empty())
{
int x;
heap.pop(x);
std::cout << x << '\n'; // will print the number from {1, 2,...999} but missing the one in the first pop
}
return 0;
}
Operations | Amortized time |
---|---|
find-min | O(1) |
delete-min | O(log n) |
insert | O(1) |
decrease-key | O(1) |
size | O(1) |
delete-all | O(n) |
- For detailed analysis of rp-heap, see [1]
A sample map taking from MMORPG Strugarden NEO
Transformed 2D grid Map
Shortest path by BFS (unweighted, 4-direction movement)
Shortest path by A* (weighted, 8-direction movement)
[1] B. Haeupler, S. Sen, and R. E. Tarjan. Rank-pairing heaps. SIAM J. Comput., 40:1463โ1485, 2011.
[2] Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996), "Shortest paths algorithms: theory and experimental evaluation", Mathematical Programming, Series A 73 (2): 129โ174, doi:10.1016/0025-5610(95)00021-6, MR 1392160