This one’s an extension that’s more likely to be used in other extensions than directly in a game. It adds a Heap data structure (~~ Priority Queue), which is a data structure that allows quick access to the smallest element of all inputs. This extension should work across the board when editors are updated (for example, it won’t work in the current microbit release, but will with the next release).
(I have another extension that relies on this one that’ll be more interesting in general; I’ll post that in a bit )
The fact that it only returns the smallest element may sound particularly limiting, but you define how elements are compared; you do this by passing a comparator
function in the constructor, which takes two objects of the given type, and should return a negative value if the first object is smaller than the second, 0 if the values are the same, or a positive value if the first value is larger than the second value.
That can definitely sound confusing at first, so a few quick examples (click details to expand):
Number min heap
const minHeap = new Heap((a: number, b: number) => a - b);
Now, when you push values into the heap, it will always give you the smallest value when you peek
or pop
:
const minHeap = new Heap((a: number, b: number) => a - b);
const values = [1, 18, -5, 256, -32, 0.0005, 82];
for (const v of values)
minHeap.push(v);
while (minHeap.length > 0)
console.log(minHeap.pop());
results in the following being logged to the console:
-32
-5
0.0005
1
18
82
256
Number max heap
If you want the exact opposite - to always get the largest value of a set of values - all you need to do is reverse the value - you can multiply the previous example by negative one, or just subtract a from b:
const maxHeap = new Heap((a: number, b: number) => b - a);
Using the same example from the previous section:
const maxHeap = new Heap((a: number, b: number) => b - a);
const values = [1, 18, -5, 256, -32, 0.0005, 82];
for (const v of values)
maxHeap.push(v);
while (maxHeap.length > 0)
console.log(maxHeap.pop());
results in
256
82
18
1
0.0005
-5
-32
Sorting Sprites by distance && Heap.BuildHeap
The heap can store any type of value; you just have to have a way to define how the elements are compared. (Note that the actual values returned don’t matter beyond whether the value is negative, 0, or positive; returning -1 will be treated the same as returning -100000)
This example will have the heap will have the heap the will always return the next sprite of kind Enemy
that is closest to the origin (0, 0):
const myEnemies = sprites.allOfKind(SpriteKind.Enemy);
const myEnemyHeap = Heap.buildHeap<Sprite>(
(a, b) => (a.x ** 2 + a.y ** 2) - (b.x ** 2 + b.y ** 2),
myEnemies
);
Note that there are two things different in this one; I defined the type by explicitly supplying the value for the generics (the <Sprite>
before the parentheses), and I’m using a different way of constructing a heap – Heap.buildHeap
.
BuildHeap is an efficient way of constructing a heap, that manages to do it faster than inserting elements one by one; it mutates the given array, and uses it for the internal storage. This version manages to complete the task in linear ( O(n)
), as compared to inserting elements one by one into the heap (O(n * log(n))
). Note that this means the heap now relies on the myEnemies
array; if you modify it, the heap will no longer necessarily work / output the correct value.
Notes
Few other notes; this is just a simple binary heap; another approach is using a fibonacci heap, but that is significantly more complicated, and almost always ends up being slower in practice even if it theoretically has lower algorithmic complexity.