MinHeap

Gives back the smallest key first. Each entry is a number key and a u32 value, a whole number from 0 to 4,294,967,295, such as an array index. A value outside that range wraps, and a SlotMap or SlotAllocator handle can be outside it, so push an index into your own array of handles. Equal keys come out in no set order, but the same pushes and pops always give the same order.

local Queue = Collections.MinHeap.new({})
Queue:Push(5, 50)
Queue:Push(2, 20)
print(Queue:Pop()) -- 2 20

Summary

Member	Description
.new()	Creates an empty heap.
:Push()	Adds an entry with Key and Value.
:Pop()	Removes and returns the entry with the smallest key.
:Peek()	Returns the entry with the smallest key without removing it.
:Count()	How many entries the heap holds.
:Clear()	Removes every entry.
Config	Settings for MinHeap.new.
MinHeap	The type MinHeap.new returns.

Functions

new

function MinHeap.new(Config: Config): MinHeap

Creates an empty heap. Errors if InitialCapacity is not a whole number.

Methods

Push

function MinHeap:Push(Key: number, Value: number)

Adds an entry with Key and Value. Raises and stores nothing when Key is NaN or not a number, or Value is not a number.

Pop

function MinHeap:Pop(): (number?, number?)

Removes and returns the entry with the smallest key.

Returns	Description
number?	the smallest key, or nil when the heap is empty
number?	its value

Peek

function MinHeap:Peek(): (number?, number?)

Returns the entry with the smallest key without removing it.

Returns	Description
number?	the smallest key, or nil when the heap is empty
number?	its value

Count

function MinHeap:Count(): number

How many entries the heap holds.

Clear

function MinHeap:Clear()

Removes every entry.

Types

Config

export type Config = { InitialCapacity: number? }

Settings for MinHeap.new.

Field	Type	Description
InitialCapacity	number?	entries to make room for up front, 8 by default

MinHeap

export type MinHeap = {
	Push: (self: MinHeap, Key: number, Value: number) -> (),
	Pop: (self: MinHeap) -> (number?, number?),
	Peek: (self: MinHeap) -> (number?, number?),
	Count: (self: MinHeap) -> number,
	Clear: (self: MinHeap) -> (),
}

The type MinHeap.new returns.