-
Notifications
You must be signed in to change notification settings - Fork 1
/
heap.go
79 lines (66 loc) · 2.53 KB
/
heap.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package heap
import (
"github.com/qulia/go-qulia/lib"
"golang.org/x/exp/constraints"
)
// Heap content type satisfy constraints.Ordered
// While comparing during heap oparation "<" is used
type Heap[T constraints.Ordered] interface {
// Insert element to the heap
Insert(T)
// Extract top element from the heap
// If heap is empty, the call will panic
Extract() T
// Size of the heap
Size() int
// IsEmpty returns true for empty heap, false otherwise
IsEmpty() bool
}
// Heap content of any type should implement lib.Comparer interface
type HeapFlex[T lib.Comparer[T]] interface {
// Insert element to the heap
Insert(T)
// Extract top element from the heap
// If heap is empty, the call will panic
Extract() T
// Size of the heap
Size() int
// IsEmpty returns true for empty heap, false otherwise
IsEmpty() bool
}
// NewMinHeapFlex initializes the heap structure from provided slice
// returned heap implements min heap properties where min value defined by
// lib.Comparer implementation of the type is at the top of the heap to be extracted first
//
// input: The input slice is cloned and will not be modified by this method
// Pass nil as input if you do not have any initial entries
func NewMinHeapFlex[T lib.Comparer[T]](input []T) HeapFlex[T] {
return newFlexImpl(input, false)
}
// NewMaxHeapFlex initializes the heap structure from provided slice.
// returned heap implements max heap properties where max value defined by
// lib.Comparer implementation of the type is at the top of the heap to be extracted first
//
// input: The input slice is cloned and will not be modified by this method.
// Pass nil as input if you do not have any initial entries
func NewMaxHeapFlex[T lib.Comparer[T]](input []T) HeapFlex[T] {
return newFlexImpl(input, true)
}
// NewMinHeap initializes the heap structure from provided slice.
// Returned heap implements heap properties using <, > operators
// of type with constraints.Ordered
//
// input: The input slice is cloned and will not be modified by this method.
// Pass nil as input if you do not have any initial entries
func NewMinHeap[T constraints.Ordered](input []T) Heap[T] {
return newImpl(input, false)
}
// NewMaxHeap initializes the heap structure from provided slice.
// Returned heap implements heap properties using <, > operators
// of type with constraints.Ordered
//
// input: The input slice is cloned and will not be modified by this method.
// Pass nil as input if you do not have any initial entries
func NewMaxHeap[T constraints.Ordered](input []T) Heap[T] {
return newImpl(input, true)
}