Skip to content

A Min/Max heap data structure for Unity. Compatible with the Unity Job system and Burst compiler.

License

Notifications You must be signed in to change notification settings

Amarcolina/NativeHeap

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

21 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Native Heap

This repo contains a very simple NativeHeap implementation for use with the new Unity Job System, Burst compiler, and DOTS. The NativeHeap data structure can be very useful when implementing many different types of algorithms, such as A-star pathfinding. It allows you to insert items into the collection with a cost of O(log(n)) per item, and it also allows you to extract them in sorted order with a cost of O(log(n)) per item.

This implementation contains a specific feature not always present in heap constructions. It allows you to remove items from the center of the collection with the same cost as removing them in-order. When an item is added, a special Index is returned that can later be used to remove the item, no matter where it is! This feature in particular is very useful when implementing a-star, since removing items from within the heap is a common operation.

How To Use It?

NativeHeap is a self-contained data structure with no dependencies, and so you can just copy NativeHeap.cs into your project and start working! Just a few considerations:

  • NativeHeap uses unsafe code, so make sure it is enabled in your project, or that NativeHeap is placed under the care of an Asmdef with unsafe code enabled.
  • You can optionally copy over the provided Min.cs and Max.cs to get a set of default comparators for built-in scalar types like int and float.
  • NativeHeap has no private members, only internal members, so if you are wary of using an unsafe method by accident just wrap the NativeHeap inside an Asmdef so that the internals are not exposed.

Parameterization

The NativeHeap is generic like NativeArray or NativeList, allowing you to store structs of type T into the collection. However unlike NativeArray or NativeList, NativeHeap has two generic parameters. The second parameter is the Comparator and is responsible for determining the ordering of the items inside the heap.

Two comparators are included, the Min and Max comparator, which are able to construct a MinHeap or a MaxHeap for the built-in csharp primitives such as int and float. Writing your own comparator is as simple as implementing the IComparer interface for the type you would like to insert. And don't worry about slowdown due to interfaces, thanks to the Burst compiler you can use custom comparators with zero extra overhead compared to integrating the comparator directly into the data structure!

Example Usage

Basic example

//Construct a new MinHeap for integers
var heap = new NativeHeap<int, Min>(Allocator.Temp);

//Insert some numbers into the heap
heap.Insert(5);
heap.Insert(3);
heap.Insert(10);

print(heap.Pop()); //3
print(heap.Pop()); //5
print(heap.Pop()); //10

//Always remember to dispose when you are finished!
heap.Dispose();

Custom comparator example

//Define a custom comparator that orders floats by their distance to the 
//constant 100
public struct DistanceTo100 : IComparer<float> {
    public int Compare(float a, float b) {
        float distForA = Mathf.Abs(a - 100.0f);
        float distForB = Mathf.Abs(b - 100.0f);
        return distForA.CompareTo(distForB);
    }
}

var heap = new NativeHeap<float, DistanceTo100>(Allocator.Temp);
...

Using an Index to remove an item

var heap = new NativeHeap<int, Min>(Allocator.Temp);

heap.Insert(5);
heap.Insert(3);
heap.Insert(10);

NativeHeapIndex indexOf7 = heap.Insert(7);

print(heap.Pop()); //3

//Remove the item 7 from the heap, even though it is
//not next up
heap.Remove(indexOf7);

print(heap.Pop()); //5
print(heap.Pop()); //10

heap.Dispose();

About

A Min/Max heap data structure for Unity. Compatible with the Unity Job system and Burst compiler.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages