Hello!
I tried to implement a min heap to make my pathfinding system work much faster, however it seems to often break when deleting the first (smallest) element.
The main functions for the min heap are the following: (Note that each element in the min-heap/priority-queue is a table that consists of a value, which is the first one, and an index, which is the second one, but the second should be irrelevant for this case)
@native
local function priorityQueue_Heapify(pq: {{number}}, i: number)
if i < 0 then
return
end
local size: number = #pq
-- Find the smallest among root, left child, and right child
local smallest: number = i
local l: number = 2 * i + 1 -- l and r are from 0 to n-1
local r: number = 2 * i + 2
if l < size and pq[i+1][1] > pq[l+1][1] then
smallest = l
end
if r < size and pq[smallest+1][1] > pq[r+1][1] then
smallest = r
end
-- Swap and continue heapifying if root is not the smallest
if smallest ~= i then
pq[i+1], pq[smallest+1] = pq[smallest+1], pq[i+1]
priorityQueue_Heapify(pq, math.floor((i+1) / 2) - 1)
end
end
@native
local function priorityQueue_Insert(pq: {{number}}, data: {number})
if #pq == 0 then
table.insert(pq, data)
else
table.insert(pq, data)
priorityQueue_Heapify(pq, math.floor(#pq / 2) - 1)
end
end
@native
local function priorityQueue_Delete(pq: {{number}}, i: number)
local size: number = #pq
pq[i+1], pq[size] = pq[size], pq[i+1]
table.remove(pq, size)
priorityQueue_Heapify(pq, math.floor((size-1) / 2) - 1)
end
And the simplest case where I was able to reproduce the issue is the following:
local pq: {{number}} = {}
for i: number = 1, 5 do
priorityQueue_Insert(pq, {i, i})
end
priorityQueue_Delete(pq, 0)
for i: number = 2, #pq do
if pq[i][1] < pq[1][1] then
print("bruh")
end
end
for _, a in pq do
print(a[1])
end
--[[
OUTPUT:
bruh (x3)
5
2
3
4
]]
Now, I have been doing experimentation here & there and found one thing that significantly increased the success rate of correctly forming the min-heap, but that was still broken. The reason I didn’t include that in the min heap code above is because every where I checked for pre-made implementations didn’t do that, so I figured it probably isn’t the right thing either. Anyways, the alternative that I found is to take the following line out of the if statement in priorityQueue_Heapify
priorityQueue_Heapify(pq, math.floor((i+1) / 2) - 1)
But as I just mentioned, that approach isn’t perfect either and doing something like this can get it to fail very easily:
local seed: number = 2
math.randomseed(seed)
local pq: {{number}} = {}
for i: number = 1, 20 do
priorityQueue_Insert(pq, {math.random(1, 10), i})
end
for i: number = 1, 10 do
priorityQueue_Delete(pq, 0)
end
for i: number = 2, #pq do
if pq[i][1] < pq[1][1] then
print("bruh")
end
end
for _, a in pq do
print(a[1])
end
As much as I can tell about the original code, it seems that the first element never gets reached after it is switched with the last one in the priorityQueue_Delete function, so it wont be appropriately switched around.
Also, I should mention that the priorityQueue_Insert function seems to work perfectly. This doesn’t neccessarely mean that the problem is in the priorityQueue_Insert function.
All the code for this is essentially translated into luau after googling an implementation and trying to understand how the min-heap works.
Any attempt to help make the min-heap is greatly appreciated!