Binary heap in C#

Unity Engine
1

Hi

I have a script which adds a lot of objects to an array and then remove the one with the lowest value (this is the basic principle, this code loops a lot of times).
Currently I use an array and iterate through it to find the lowest value.
I have heard of something called binary heaps which should be able to do this much faster.
Can anyone show me how to implement one?
Or is there a even faster way of doing this?

2

BinaryHeaps are pretty simple. the following page should give you a good idea: David Cumps - Binary Heaps

3

Thanks.

But that tutorial was only half way through, the code was referring to a lot of things he didn’t explain.

4

Like which one in detail?

A heap isn’t anything else than Add and Remove and sift down / bubble up elements in the “tree” as needed to comply to the requirements.

the only things he does not explain are the trivial ones due to this naming, like variables that are not declared but that are private class variables (numberOfItems which contains the first free index in the array and is initialized at 1 and changed by add and remove automatically)

5

Like the base class.
What variables you need to use and the functions for iterating through it (I don’t know how to write one).

6

Its an own datastructure, it does not base on another one, so the answer is none.

all you need to add around it is something like:

using System;

public class BinaryHeap {
   private System.Object BinaryHeap[];
   private int numberOfItems;

   public BinaryHeap( int numberOfElements ) {
     BinaryHeap = new System.Object[numberOfElements];
     numberOfItems = 1;
   }

   /*
    * add the functions here
    */

}

I thought you were interested in knowing how it works to implement one and that article contains all information on that, you just need to be interested to implement it, which is straight forward if you understood the two functions.

If you are looking for a working solution you can just plugin, you should mention that …

1 Like
7

Now it works, and my script it of some reason 7 times faster because of that :smile:

Thanks!

8

glad it works :slight_smile:

And yupp, binary heaps are lightning fast especially if you use them for things like priority queues.

haven’t seen many structures able to compete for this operations.

For sort, there are faster solutions

1 Like