Godot binaryHeap implement

binary_heap.gd

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