[Wally] MinHeap: A highly optimized, array-backed Priority Queue

Resources Community Resources
, , , ,
1

MinHeap | A highly optimized, array-backed Priority Queue

Built for high-performance scheduling and zero-GC idling.

:package: Get it on Wally | :laptop: View Source on GitHub

Most priority queues on the DevForum work fine for small lists, but as they scale up, they choke the GC (Garbage Collector) or cause massive frame drops. I needed a scheduling structure for a high-performance custom streaming system, so I built this: a mathematically strict, purely array-backed Min-Heap.

It is designed to be completely memory-safe, zero-GC on idle, and scales infinitely until it physically hits the Luau Virtual Machine limits.

:high_voltage: The Performance Test

Because it perfectly maintains an O(log N) time complexity for both Insert() and Extract(), the speed remains consistent regardless of how deep the tree gets.

In exponential stress testing, the heap achieved the following metrics in a single frame execution:

  • 10,000 Elements: ~0.015 seconds
  • 100,000 Elements: ~0.28 seconds
  • 1,000,000 Elements: ~5.07 seconds
📉 View the Exponential Stress Test Logs (10M+ Elements) 
  18:36:09.726  ================================================== 
  18:36:09.726     STARTING MIN-HEAP EXPONENTIAL STRESS TEST       
  18:36:09.726  ================================================== 
  
--- Step 1: Testing Heap Size = 10 elements (1000 iterations) --- 
  18:36:12.108    [SUCCESS] Total Cycle: 0.00001s | Insert: 0.00000s | Extract: 0.00000s 
  18:36:12.108    [MEMORY] Estimated Delta: 0.00 MB 
  
--- Step 2: Testing Heap Size = 100 elements (1000 iterations) --- 
  18:36:12.775    [SUCCESS] Total Cycle: 0.00009s | Insert: 0.00003s | Extract: 0.00005s 
  18:36:12.775    [MEMORY] Estimated Delta: 0.04 MB 
  
--- Step 3: Testing Heap Size = 1,000 elements (100 iterations) --- 
  18:36:13.388    [SUCCESS] Total Cycle: 0.00110s | Insert: 0.00034s | Extract: 0.00076s 
  18:36:13.388    [MEMORY] Estimated Delta: 0.08 MB 
  
--- Step 4: Testing Heap Size = 10,000 elements (50 iterations) --- 
  18:36:14.763    [SUCCESS] Total Cycle: 0.01584s | Insert: 0.00386s | Extract: 0.01198s 
  18:36:14.764    [MEMORY] Estimated Delta: 2.50 MB 
  
--- Step 5: Testing Heap Size = 100,000 elements (5 iterations) --- 
  18:36:16.713    [SUCCESS] Total Cycle: 0.28654s | Insert: 0.04359s | Extract: 0.24295s 
  18:36:16.713    [MEMORY] Estimated Delta: 11.51 MB 
  
--- Step 6: Testing Heap Size = 1,000,000 elements (1 iterations) --- 
  18:36:22.301    [SUCCESS] Total Cycle: 5.07470s | Insert: 0.48514s | Extract: 4.58956s 
  18:36:22.301    [MEMORY] Estimated Delta: 110.83 MB 
  
--- Step 7: Testing Heap Size = 10,000,000 elements (1 iterations) --- 
  18:38:00.459    [SUCCESS] Total Cycle: 97.57064s | Insert: 5.27232s | Extract: 92.29832s 
  18:38:00.459    [MEMORY] Estimated Delta: 1201.30 MB 
  
--- Step 8: Testing Heap Size = 100,000,000 elements (1 iterations) --- 
  
================================================== 
    CRASH / LIMIT REACHED AT 100000000 ELEMENTS! 
    Error: ServerScriptService.Server.Systems.StreamingScheduler.MinHeap:47: table overflow 
==================================================

The Limit: The module has no artificial ceiling. It only crashes at ~100 million elements because it hits the array limit.

:sparkles: Features

  • Purely Array-Backed: No node objects, no metatables. The binary tree is mapped entirely via mathematical indexes (2i and 2i + 1), preventing massive memory allocations.
  • Zero-GC: ‘Bypasses’ garbage collection micro-stutters by avoiding constant table creation/destruction during idle states.

:package: Installation

Method 1: Wally (Recommended)
Add this to your wally.toml file:

minheap = "ijustwork/minheap@0.1.0"

Method 2: Direct Download
Grab the latest .luau file release directly from the GitHub Repository.

:laptop: API & Usage

local MinHeap = require(path.to.MinHeap)

-- 1. Create a new heap
local myHeap = MinHeap.new()

-- 2. Insert data (Data, Priority)
-- Lower priority numbers rise to the top of the queue.
myHeap:Insert("Zombie_01", 50)
myHeap:Insert("Zombie_02", 10)
myHeap:Insert("Boss_Entity", 1) 

-- 3. Extract the highest priority item (O(1) access, O(log N) sink)
local nextEntity = myHeap:Extract()
print(nextEntity) -- Outputs: "Boss_Entity"

Small note

This is the first time I release a public resource, so please bare with me if I haven’t mentioned anything, if there are any bugs or so on. I’m open to any and all suggestions, bug reports and reconstructive criticism!

5 Likes
2

If you wanna optimize it even more later, there are a few things you could do if you wanna squeeze in extra performance

Instead of creating a { Priority, Value } table for every node, you could store priorities and values in two separate arrays. That avoids creating a bunch of tiny tables, which means less garbage collection.

You could also replace table.insert() and table.remove() by keeping track of the heap size yourself. Writing directly to array indices is a bit faster and avoids the extra function call overhead.

For _SiftUp() and _SiftDown(), you could shift elements instead of constantly swapping them. Just keep the node you’re moving in a variable, slide everything else over until you find the right spot, then insert it once. That reduces the number of assignments.

Also, if you ever need to build a heap from existing data, you could add a heapify constructor instead of inserting every item individually. Pairing that with table.create() for preallocating memory and table.clear() for reusing tables can help reduce allocations and keep memory usage a little cleaner

1 Like