Skip to main content

Heap

A generic Heap implementation for both min and max heaps. It is designed for allowing the association of a cost to a given value so that users are not restricted to just numbers as values.

What is a Heap?

Heaps are an implementation of Priority Queues that excel at tracking the smallest or largest element in an array. They are commonly used in algorithms like Dijkstra's shortest path algorithm and Huffman coding.

Examples:

local minHeap = Heap.min()
minHeap:Push("A", 5) -- A is the value, and 5 is the cost associated with it
minHeap:Push("B", 2)
minHeap:Push("C", 8)
minHeap:Push("D", 4)

-- look at the current lowest value
local minValue, minCost = minHeap:Peek()
print(minValue, minCost) -- B 2

local maxHeap = Heap.max()
minHeap:Push("A", 5)
minHeap:Push("B", 2)
minHeap:Push("C", 8)
minHeap:Push("D", 4)

local poppedValue, costOfPoppedValue = maxHeap:Pop() -- pops off the top value
print(poppedValue, costOfPoppedValue) -- C 8

-- look at the new highest value
print(maxHeap:Peek()) -- A 5
MetaMethods

Supports the following metamethods:

  • __tostring: Returns a string representation of the heap in a tree like display.
  • __len: Returns the number of elements in the heap. Equivalent to calling :Size(). 
    local minHeap = Heap.min()
minHeap:Push("A", 5)
minHeap:Push("B", 2)
print(#minHeap) -- 2
  • __iter: Provides an iterator for for loop usage
Exported Types

This file exports a Heap type in the form of Heap<T> where T is the type of value stored in the heap. Usually Luau can infer the type of T from your usage, but it may be useful to manually provide the type if you are using more complex datatypes. 

local Heap = require(ReplicatedStorage.Heap)
type Heap<T> = Heap.Heap<T>

local myHeap: Heap<string> = Heap.min()
myHeap:Push("A", 5)
Info for Nerds

Read this only if you want to know more about the internals of this heap implmenentation.

In order to support the association of a cost to a value, the heap is implemented as three separate arrays. One to store the values, one to store the costs, and one to store the index pointing to the first two. I used this structure in order to optimize for cache hits on table lookups since using an object based approach Ex: {Value: T, Cost: number} could cause the CPU to potentially miss the Cost data since it may not be stored continguously in memory.

When a value is popped from the heap, its reference index is stored in a stack of open indices for reuse. This is done to hopefully reduce fragmentation of the heap and improve the likelyhood of cache hits.

I originally opted to use a dynamic cost system such that you would provide a comparator function to the constructor that would be used to determine the cost of each value. However, this introduced a number of potential issues such as if the comparator function was not deterministic, causing the order to desync. There could very likely be cases where the cost could change without the heap's knowledge of it. So instead I opted to require the cost to be provided at the time of insertion. Although technically the type definition specifies for only number costs, you could in theory use any type luau considers comparable with relational operators.

Functions​

min​

static
</>
Heap.min() → Heap<T>--

A min-heap instance.

Creates a min-heap where the smallest element is always on top.

max​

static
</>
Heap.max() → Heap<T>--

A max-heap instance.

Creates a max-heap where the largest element is always on top.

Peek​

</>
Heap:Peek() → (
T?,--

The top value from the heap.

number?--

The cost of the top value.

)

Returns the top value from the heap without removing it. The top value is the value with the lowest cost in a min-heap and the value with the highest cost in a max-heap. If the heap is empty, nil is returned for both values.

Time Complexity: Runs in O(1) time.

Push​

</>
Heap:Push(
value: T,
cost: number?
) → ()

Inserts a value into the heap.

Time Complexity: Runs in worst case O(log n) time.

local minHeap = Heap.min()

minHeap:Push("A", 5)
minHeap:Push("B", 2)
minHeap:Push("C", 8)

local minValue, minCost = minHeap:Peek()
print(minValue, minCost) -- B 2
Cost

If no cost is given, the value itself is used as the cost. Ensure that the given value is comparable with relational operators. 

local minHeap = Heap.min()
minHeap:Push(2) -- uses 2 for both value and cost
print(minHeap:Peek()) -- 2 2

Pop​

</>
Heap:Pop() → (
T?,
number?
)

Removes and returns the top value from the heap.

Time Complexity: Runs in worst case O(log n) time.

Size​

</>
Heap:Size() → number

Returns the number of elements in the heap. Equivalent to using the # operator on the heap.

Time Complexity: Runs in O(1) time.

Has​

</>
Heap:Has(
valueToCheckFor: T,
cost: number?
) → boolean

Takes a value or function and checks if the heap contains it. If a cost is provided then it will also ensure the cost matches. Returns true if the heap contains a specified value.

Time Complexity: Runs in worst case O(n) time.

UpdateCost​

unreleased
</>
Heap:UpdateCost(
valueToUpdate: T | (value: T) → (boolean),--

The value to update the cost of.

newCost: number | (
value: T,
oldCost: number
) → number,--

The new cost to assign to the value. Can also be a function that takes the old cost and returns a new cost.

updateAll: boolean?--

If true, all occurrences of the value will be updated. Defaults to false.

) → boolean--

True if the cost was updated, false otherwise.

Updates the cost of a value in the heap. If no value is found, false is returned.

Repeated Values

If you have multiple instances of the same value, this method will only update the cost of the first valid instance found, unless the third parameter updateAll is set to true. There is no guarantee of which instance will be found first. Using updateAll can be expensive as it may need to perform a large resorting of the heap to ensure proper ordering. 

local minHeap = Heap.min()
minHeap:Push("A", 5)
minHeap:Push("B", 2)
minHeap:Push("C", 8)
minHeap:Push("D", 10)

print(minHeap:Peek()) -- B 2
minHeap:UpdateCost("A", 1)
print(minHeap:Peek()) -- A 1

    -- update the cost of the first value that matches either "A" or "B" to 15
minHeap:UpdateCost(function(value)
    return value == "A" or value == "B"
end, 15, false)

-- update the cost of all values that match "A" or "B" to 30
minHeap:UpdateCost(function(value)
    return value == "A" or value == "B"
end, 30, true)

RemoveFirstOccurrence​

</>
Heap:RemoveFirstOccurrence(valueToRemove: T) → boolean

Removes the first occurrence of a given value from the heap. Heaps are not optimized for search removals, so this method should be used sparingly.

RemoveAllOccurrences​

</>
Heap:RemoveAllOccurrences(valueToRemove: T) → number

Removes all occurrences of a value from the heap and returns the number of occurrences removed. Heaps are not optimized for search removals, so this method should be used sparingly.

ToTree​

</>
Heap:ToTree() → Branch<T>?--

A tree representation of the heap.

A utility method that converts the heap into a tree structure. This is useful for debugging and visualizing the heap.

type Branch<T> = {Value: T, Left: Branch<T>?, Right: Branch<T>?}

iterating over Heap​

metamethod
</>
for  value: T, cost: number  in  Heap  do

MetaMethod for iterating over the heap. In a for loop, the first variable is the Value and the second variable is the Cost. 

local minHeap = Heap.min()
minHeap:Push("A", 5)
minHeap:Push("B", 2)
minHeap:Push("C", 8)
minHeap:Push("A", 4)
minHeap:Push("D", 10)

for value: string, cost: number in minHeap do
    print(value, cost)
end

-- Output: the order may vary
B 2
A 4
C 8
A 5
D 10
Manipulating the Heap during iteration

It is not recommended to modify the Heap during iteration as it may cause undefined behavior. Internal orders may change and the iterator may not be able to find the next value.

Iteration Order

There is no guaranteed order of iteration. You should assume you will receive the values in a random order.

Show raw api
{
    "functions": [
        {
            "name": "min",
            "desc": "Creates a min-heap where the smallest element is always on top.",
            "params": [],
            "returns": [
                {
                    "desc": "A min-heap instance.",
                    "lua_type": "Heap<T>"
                }
            ],
            "function_type": "static",
            "tags": [
                "static"
            ],
            "source": {
                "line": 169,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "max",
            "desc": "Creates a max-heap where the largest element is always on top.",
            "params": [],
            "returns": [
                {
                    "desc": "A max-heap instance.",
                    "lua_type": "Heap<T>"
                }
            ],
            "function_type": "static",
            "tags": [
                "static"
            ],
            "source": {
                "line": 178,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "Peek",
            "desc": "Returns the *top value* from the heap without removing it.\nThe top value is the value with the lowest cost in a min-heap \nand the value with the highest cost in a max-heap.\nIf the heap is empty, nil is returned for both values.\n\n\n*Time Complexity:* Runs in `O(1)` time.",
            "params": [],
            "returns": [
                {
                    "desc": "The top value from the heap.",
                    "lua_type": "T?"
                },
                {
                    "desc": "The cost of the top value.",
                    "lua_type": "number?"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 197,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "Push",
            "desc": "Inserts a value into the heap.\n\n*Time Complexity:* Runs in worst case `O(log n)` time.\n\n```lua\nlocal minHeap = Heap.min()\n\nminHeap:Push(\"A\", 5)\nminHeap:Push(\"B\", 2)\nminHeap:Push(\"C\", 8)\n\nlocal minValue, minCost = minHeap:Peek()\nprint(minValue, minCost) -- B 2\n```\n\n:::info Cost\nIf no **cost** is given, the value itself is used as the cost.\nEnsure that the given value is comparable with relational operators.\n```lua\nlocal minHeap = Heap.min()\nminHeap:Push(2) -- uses 2 for both value and cost\nprint(minHeap:Peek()) -- 2 2\n```\n:::",
            "params": [
                {
                    "name": "value",
                    "desc": "",
                    "lua_type": "T"
                },
                {
                    "name": "cost",
                    "desc": "",
                    "lua_type": "number?"
                }
            ],
            "returns": [],
            "function_type": "method",
            "source": {
                "line": 229,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "Pop",
            "desc": "Removes and returns the top value from the heap.\n\n*Time Complexity:* Runs in worst case `O(log n)` time.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "T?"
                },
                {
                    "desc": "",
                    "lua_type": "number?"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 257,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "Size",
            "desc": "Returns the number of elements in the heap.\nEquivalent to using the `#` operator on the heap.\n\n*Time Complexity:* Runs in `O(1)` time.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 291,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "Has",
            "desc": "Takes a value or function and checks if the heap contains it.\nIf a cost is provided then it will also ensure the cost matches.\nReturns true if the heap contains a specified value.\n\n*Time Complexity:* Runs in worst case `O(n)` time.",
            "params": [
                {
                    "name": "valueToCheckFor",
                    "desc": "",
                    "lua_type": "T"
                },
                {
                    "name": "cost",
                    "desc": "",
                    "lua_type": "number?"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 302,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "ToArray",
            "desc": "Converts the heap into an array of `{Value: T, Cost: number}` objects.\nThis is useful for iterating over the heap in a more structured way\nwithout the worry of it changing during iteration.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{{Value: T, Cost: number}}"
                }
            ],
            "function_type": "method",
            "private": true,
            "unreleased": true,
            "source": {
                "line": 322,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "UpdateCost",
            "desc": "Updates the cost of a value in the heap. If no value is found, false is returned.\n:::caution Repeated Values\nIf you have multiple instances of the same value, this method will only update the cost of the first valid instance found,\nunless the third parameter `updateAll` is set to `true`. There is no guarantee of which instance will be found first.\nUsing `updateAll` can be expensive as it may need to perform a large resorting of the heap to ensure proper ordering.\n:::\n\n```lua\nlocal minHeap = Heap.min()\nminHeap:Push(\"A\", 5)\nminHeap:Push(\"B\", 2)\nminHeap:Push(\"C\", 8)\nminHeap:Push(\"D\", 10)\n\nprint(minHeap:Peek()) -- B 2\nminHeap:UpdateCost(\"A\", 1)\nprint(minHeap:Peek()) -- A 1\n```\n```lua\n    -- update the cost of the first value that matches either \"A\" or \"B\" to 15\nminHeap:UpdateCost(function(value)\n    return value == \"A\" or value == \"B\"\nend, 15, false)\n\n-- update the cost of all values that match \"A\" or \"B\" to 30\nminHeap:UpdateCost(function(value)\n    return value == \"A\" or value == \"B\"\nend, 30, true)\n```",
            "params": [
                {
                    "name": "valueToUpdate",
                    "desc": "The value to update the cost of.",
                    "lua_type": "T | (value: T) -> (boolean)"
                },
                {
                    "name": "newCost",
                    "desc": "The new cost to assign to the value. Can also be a function that takes the old cost and returns a new cost.",
                    "lua_type": "number | (value: T, oldCost: number) -> number"
                },
                {
                    "name": "updateAll",
                    "desc": "If true, all occurrences of the value will be updated. Defaults to false.",
                    "lua_type": "boolean?\r\n"
                }
            ],
            "returns": [
                {
                    "desc": "True if the cost was updated, false otherwise.",
                    "lua_type": "boolean"
                }
            ],
            "function_type": "method",
            "unreleased": true,
            "source": {
                "line": 366,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "GetCost",
            "desc": "*This has been removed from the public API Docs as it can be\nachieved by iterating over the heap and counting the occurrences.*\n\nReturns the cost given to a value. If no value is found, nil is returned.\n:::caution Repeated Values\nIf you have multiple instances of the same value, this method will return the cost of the first instance found.\nThere is no guarantee of which instance will be found first.\n:::",
            "params": [
                {
                    "name": "valueToCheckCostOf",
                    "desc": "",
                    "lua_type": "T"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number?\r\n"
                }
            ],
            "function_type": "method",
            "private": true,
            "source": {
                "line": 434,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "CountOccurrences",
            "desc": "Returns the number of occurrences of a value in the heap.\n\n*This has been removed from the public API Docs as it can be\nachieved by iterating over the heap and counting the occurrences.*\n\n*Time Complexity:* Runs in `O(n)` time.",
            "params": [
                {
                    "name": "valueToCheckFor",
                    "desc": "",
                    "lua_type": "T"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number\r\n"
                }
            ],
            "function_type": "method",
            "private": true,
            "source": {
                "line": 455,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "RemoveFirstOccurrence",
            "desc": "Removes the first occurrence of a given value from the heap.\nHeaps are not optimized for search removals, so this method should\nbe used sparingly.",
            "params": [
                {
                    "name": "valueToRemove",
                    "desc": "",
                    "lua_type": "T"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 470,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "RemoveAllOccurrences",
            "desc": "Removes all occurrences of a value from the heap and returns the\nnumber of occurrences removed. Heaps are not optimized for search \nremovals, so this method should be used sparingly.",
            "params": [
                {
                    "name": "valueToRemove",
                    "desc": "",
                    "lua_type": "T"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number\r\n"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 499,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "ToTree",
            "desc": "A utility method that converts the heap into a tree structure.\nThis is useful for debugging and visualizing the heap.\n\n`type Branch<T> = {Value: T, Left: Branch<T>?, Right: Branch<T>?}`",
            "params": [],
            "returns": [
                {
                    "desc": "A tree representation of the heap.",
                    "lua_type": "Branch<T>?"
                }
            ],
            "function_type": "method",
            "source": {
                "line": 531,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "_heapifyUp",
            "desc": "Restores the heap order by moving a node up towards the root.\n\nThis is excessively large bc splitting the min/max heap comparators reduces\nthe number of comparisons each loop. Its not a huge performance boost, but\nit is a performance boost.",
            "params": [
                {
                    "name": "index",
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "returns": [],
            "function_type": "method",
            "private": true,
            "source": {
                "line": 555,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "_heapifyDown",
            "desc": "Restores the heap order by moving a node down towards the leaves.\n\nThis is excessively large bc splitting the min/max heap comparators reduces\nthe number of comparisons each loop. Its not a huge performance boost, but\nit is a performance boost.",
            "params": [
                {
                    "name": "index",
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "returns": [],
            "function_type": "method",
            "private": true,
            "source": {
                "line": 592,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "__len",
            "desc": "Metamethod for the len operator `#`.\n\nReturns the number of elements in the heap.\n```lua\nlocal minHeap = Heap.min()\nminHeap:Push(\"A\", 5)\nminHeap:Push(\"B\", 2)\nprint(#minHeap) -- 2\n```",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number\r\n"
                }
            ],
            "function_type": "method",
            "tags": [
                "metamethod"
            ],
            "private": true,
            "source": {
                "line": 650,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "__tostring",
            "desc": "Metamethod for tostring.\n\nAttempts to return a string representation of the heap in a tree like display.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "string\r\n"
                }
            ],
            "function_type": "method",
            "tags": [
                "metamethod"
            ],
            "private": true,
            "source": {
                "line": 661,
                "path": "lib/heap/src/init.luau"
            }
        },
        {
            "name": "__iter",
            "desc": "MetaMethod for iterating over the heap.\nIn a for loop, the first variable is the `Value` and the second variable is the `Cost`.\n\n```lua\nlocal minHeap = Heap.min()\nminHeap:Push(\"A\", 5)\nminHeap:Push(\"B\", 2)\nminHeap:Push(\"C\", 8)\nminHeap:Push(\"A\", 4)\nminHeap:Push(\"D\", 10)\n\nfor value: string, cost: number in minHeap do\n    print(value, cost)\nend\n```\n```\n-- Output: the order may vary\nB 2\nA 4\nC 8\nA 5\nD 10\n```\n\n:::caution Manipulating the Heap during iteration\nIt is not recommended to modify the Heap during iteration as it may cause undefined behavior.\nInternal orders may change and the iterator may not be able to find the next value.\n:::\n\n:::caution Iteration Order\nThere is no guaranteed order of iteration. You should assume you will receive the values in a random order.\n:::",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "value: T"
                },
                {
                    "desc": "",
                    "lua_type": "cost: number"
                }
            ],
            "function_type": "method",
            "tags": [
                "metamethod"
            ],
            "source": {
                "line": 723,
                "path": "lib/heap/src/init.luau"
            }
        }
    ],
    "properties": [
        {
            "name": "ClassName",
            "desc": "Just a simple string identifier for the class name.",
            "lua_type": "\"Heap\"",
            "tags": [
                "static"
            ],
            "private": true,
            "source": {
                "line": 147,
                "path": "lib/heap/src/init.luau"
            }
        }
    ],
    "types": [],
    "name": "Heap",
    "desc": "A generic [Heap](https://en.wikipedia.org/wiki/Heap_(data_structure)) implementation for both min and max heaps. It is designed\nfor allowing the association of a cost to a given value so that users are not restricted to just numbers as values.\n\n### *What is a Heap?*\nHeaps are an implementation of [Priority Queues](https://en.wikipedia.org/wiki/Priority_queue) that excel at tracking the smallest\nor largest element in an array. They are commonly used in algorithms like Dijkstra's shortest path algorithm and Huffman coding.\n\n### Examples:\n\n```lua title=\"Min Heap\"\nlocal minHeap = Heap.min()\nminHeap:Push(\"A\", 5) -- A is the value, and 5 is the cost associated with it\nminHeap:Push(\"B\", 2)\nminHeap:Push(\"C\", 8)\nminHeap:Push(\"D\", 4)\n\n-- look at the current lowest value\nlocal minValue, minCost = minHeap:Peek()\nprint(minValue, minCost) -- B 2\n```\n```lua title=\"Max Heap\"\nlocal maxHeap = Heap.max()\nminHeap:Push(\"A\", 5)\nminHeap:Push(\"B\", 2)\nminHeap:Push(\"C\", 8)\nminHeap:Push(\"D\", 4)\n\nlocal poppedValue, costOfPoppedValue = maxHeap:Pop() -- pops off the top value\nprint(poppedValue, costOfPoppedValue) -- C 8\n\n-- look at the new highest value\nprint(maxHeap:Peek()) -- A 5\n```\n\n___\n:::tip MetaMethods\nSupports the following metamethods:\n- `__tostring`: Returns a string representation of the heap in a tree like display.\n- [`__len`](/api/Heap#Size): Returns the number of elements in the heap. Equivalent to calling [`:Size()`](/api/Heap#Size).\n    ```lua\n    local minHeap = Heap.min()\n    minHeap:Push(\"A\", 5)\n    minHeap:Push(\"B\", 2)\n    print(#minHeap) -- 2\n    ```\n- [`__iter`](/api/Heap#__iter): Provides an iterator for for loop usage\n:::\n\n:::tip Exported Types\nThis file exports a Heap type in the form of **`Heap<T>`** where **`T`** is the type of value stored in the heap.\nUsually Luau can infer the type of **`T`** from your usage, but it may be useful to manually provide the type if\nyou are using more complex datatypes.\n```lua\nlocal Heap = require(ReplicatedStorage.Heap)\ntype Heap<T> = Heap.Heap<T>\n\nlocal myHeap: Heap<string> = Heap.min()\nmyHeap:Push(\"A\", 5)\n```\n:::\n\n:::info Info for Nerds\n*Read this only if you want to know more about the internals of this heap implmenentation.*\n\nIn order to support the association of a cost to a value, the heap is implemented as three separate arrays.\nOne to store the values, one to store the costs, and one to store the index pointing to the first two.\nI used this structure in order to optimize for cache hits on table lookups since using an object based \napproach `Ex: {Value: T, Cost: number}` could cause the CPU to potentially miss the `Cost` data since it may\nnot be stored continguously in memory.\n\nWhen a value is popped from the heap, its reference index is stored in a stack of open indices for reuse.\nThis is done to hopefully reduce fragmentation of the heap and improve the likelyhood of cache hits.\n\nI originally opted to use a dynamic cost system such that you would provide a comparator function\nto the constructor that would be used to determine the cost of each value. However, this introduced\na number of potential issues such as if the comparator function was not deterministic, causing the order to desync.\nThere could very likely be cases where the cost could change without the heap's knowledge of it. So instead I opted\nto require the cost to be provided at the time of insertion. Although technically the type definition specifies for\nonly number costs, you could in theory use any type luau considers comparable with relational operators.\n:::",
    "source": {
        "line": 86,
        "path": "lib/heap/src/init.luau"
    }
}