v

1
module datatypes
2

3
// MinHeap is a binary minimum heap data structure.
4
pub struct MinHeap[T] {
5
mut:
6
	data []T
7
}
8

9
// insert adds an element to the heap.
10
pub fn (mut heap MinHeap[T]) insert(item T) {
11
	// push item to the end of the array
12
	heap.data << item
13
	// swap the new node with its parent until the heap is in order
14
	mut child := heap.data.len - 1
15
	mut parent := heap.parent(child)
16
	for heap.data[parent] > heap.data[child] {
17
		heap.data[parent], heap.data[child] = heap.data[child], heap.data[parent]
18
		child = parent
19
		parent = heap.parent(child)
20
	}
21
}
22

23
// insert array of elements to the heap.
24
pub fn (mut heap MinHeap[T]) insert_many(elements []T) {
25
	for v in elements {
26
		heap.insert(v)
27
	}
28
}
29

30
// pop removes the top-most element from the heap.
31
pub fn (mut heap MinHeap[T]) pop() !T {
32
	if heap.data.len == 0 {
33
		return error('Heap is empty')
34
	} else if heap.data.len == 1 {
35
		return heap.data.pop()
36
	}
37
	item := heap.data[0]
38
	// move last element to root
39
	heap.data[0] = heap.data.pop()
40
	// swap the new root with its minimum child until the heap is in order
41
	mut parent := 0
42
	mut left := heap.left_child(parent) or { return item }
43
	mut right := heap.right_child(parent) or { left }
44
	for heap.data[parent] > heap.data[left] || heap.data[parent] > heap.data[right] {
45
		// choose min for min heap
46
		swap := if heap.data[left] <= heap.data[right] { left } else { right }
47
		heap.data[parent], heap.data[swap] = heap.data[swap], heap.data[parent]
48
		parent = swap
49
		left = heap.left_child(parent) or { break }
50
		right = heap.right_child(parent) or { left }
51
	}
52
	return item
53
}
54

55
// peek gets the top-most element from the heap without removing it.
56
pub fn (heap MinHeap[T]) peek() !T {
57
	if heap.data.len == 0 {
58
		return error('Heap is empty')
59
	}
60
	return heap.data[0]
61
}
62

63
// len returns the number of elements in the heap.
64
pub fn (heap MinHeap[T]) len() int {
65
	return heap.data.len
66
}
67

68
// left_child is a helper function that returns the index of the left
69
// child given a parent idx, or none if there is no left child.
70
fn (heap MinHeap[T]) left_child(idx int) !int {
71
	child := 2 * idx + 1
72
	if child >= heap.data.len {
73
		return error('none')
74
	}
75
	return child
76
}
77

78
// right_child is a helper function that returns the index of the right
79
// child given a parent idx, or none if there is no right child.
80
fn (heap MinHeap[T]) right_child(idx int) !int {
81
	child := 2 * idx + 2
82
	if child >= heap.data.len {
83
		return error('none')
84
	}
85
	return child
86
}
87

88
// parent is a helper function that returns the parent index of the child.
89
fn (heap MinHeap[T]) parent(idx int) int {
90
	return (idx - 1) / 2
91
}
92