Skip to content

Instantly share code, notes, and snippets.

@citizenll
Created May 30, 2023 02:07
Show Gist options
  • Save citizenll/4821ef5baaea8d88e058b6eac05c3bfc to your computer and use it in GitHub Desktop.
Save citizenll/4821ef5baaea8d88e058b6eac05c3bfc to your computer and use it in GitHub Desktop.
Godot binaryHeap implement
class_name BinaryHeap
var items:Array = []
var sort_func:Callable
func _init(initial_items=null, custom_sort=null):
if custom_sort != null:
sort_func = custom_sort
else:
sort_func = time_sort_func
if initial_items != null:
for i in initial_items:
push(i)
func impl():
return items
func size():
return items.size()
func peek():
if items.size() == 0:
return null
return items[0]
func push(item):
items.append(item)
heapify_up(items.size() - 1)
func pop():
if items.size() == 0:
return null
swap(0, items.size() - 1)
var item = items.pop_back()
heapify_down(0)
return item
func remove(item):
var index = items.find(item)
if index == -1:
return
swap(index, items.size() - 1)
items.pop_back()
heapify_down(index)
func heapify_up(index):
var parent = (index - 1) / 2
if parent < 0:
return
#use sort func
if sort_func.call(items[parent], items[index]) > 0:
swap(parent, index)
heapify_up(parent)
func heapify_down(index):
var left = index * 2 + 1
var right = index * 2 + 2
if left >= items.size():
return
if right >= items.size():
if sort_func.call(items[left], items[index]) < 0:
swap(left, index)
heapify_down(left)
return
if sort_func.call(items[left], items[right]) < 0:
if sort_func.call(items[left], items[index]) < 0:
swap(left, index)
heapify_down(left)
else:
if sort_func.call(items[right], items[index]) < 0:
swap(right, index)
heapify_down(right)
func swap(a, b):
var temp = items[a]
items[a] = items[b]
items[b] = temp
func time_sort_func(a, b) -> int:
return a.next_time - b.next_time
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment