# Heap
Heap is a binary heap tree implemented by slice.
# Source
# Usage
import (
heap "github.com/duke-git/lancet/v2/datastructure/heap"
)
# Index
# Documentation
# 1. MaxHeap
MaxHeap is a binary heap tree implemented by slice, The key of the root node is both greater than or equal to the key value of the left subtree and greater than or equal to the key value of the right subtree.
# NewMaxHeap
Return a NewMaxHeap pointer instance.
Signature:
type MaxHeap[T any] struct {
data []T
comparator lancetconstraints.Comparator
}
func NewMaxHeap[T any](comparator lancetconstraints.Comparator) *MaxHeap[T]
Example:
package main
import (
"fmt"
heap "github.com/duke-git/lancet/v2/datastructure/heap"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
maxHeap := heap.NewMaxHeap[int](&intComparator{})
fmt.Println(maxHeap)
}
# Push
Push value into the heap
Signature:
func (h *MaxHeap[T]) Push(value T)
Example:
package main
import (
"fmt"
heap "github.com/duke-git/lancet/v2/datastructure/heap"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
maxHeap := heap.NewMaxHeap[int](&intComparator{})
values := []int{6, 5, 2, 4, 7, 10, 12, 1, 3, 8, 9, 11}
for _, v := range values {
maxHeap.Push(v)
}
fmt.Println(maxHeap.Data()) //[]int{12, 9, 11, 4, 8, 10, 7, 1, 3, 5, 6, 2}
}
# Pop
Pop return the largest value, and remove it from the heap if heap is empty, return zero value and fasle
Signature:
func (h *MaxHeap[T]) Pop() (T, bool)
Example:
package main
import (
"fmt"
heap "github.com/duke-git/lancet/v2/datastructure/heap"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
maxHeap := heap.NewMaxHeap[int](&intComparator{})
values := []int{6, 5, 2, 4, 7, 10, 12, 1, 3, 8, 9, 11}
for _, v := range values {
maxHeap.Push(v)
}
val, ok := maxHeap.Pop()
fmt.Println(val) //12
fmt.Println(ok) //true
}
# Peek
Return the largest element from the heap without removing it, if heap is empty, it returns zero value and false.
Signature:
func (h *MaxHeap[T]) Peek() (T, bool)
Example:
package main
import (
"fmt"
heap "github.com/duke-git/lancet/v2/datastructure/heap"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
maxHeap := heap.NewMaxHeap[int](&intComparator{})
values := []int{6, 5, 2, 4, 7, 10, 12, 1, 3, 8, 9, 11}
for _, v := range values {
maxHeap.Push(v)
}
val, ok := maxHeap.Peek()
fmt.Println(val) //12
fmt.Println(maxHeap.Size()) //12
}
# Data
Return all element of the heap
Signature:
func (h *MaxHeap[T]) Data() []T
Example:
package main
import (
"fmt"
heap "github.com/duke-git/lancet/v2/datastructure/heap"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
maxHeap := heap.NewMaxHeap[int](&intComparator{})
values := []int{6, 5, 2, 4, 7, 10, 12, 1, 3, 8, 9, 11}
for _, v := range values {
maxHeap.Push(v)
}
fmt.Println(maxHeap.Data()) //[]int{12, 9, 11, 4, 8, 10, 7, 1, 3, 5, 6, 2}
}
# Size
Return the number of elements in the heap
Signature:
func (h *MaxHeap[T]) Size() int
Example:
package main
import (
"fmt"
heap "github.com/duke-git/lancet/v2/datastructure/heap"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
maxHeap := heap.NewMaxHeap[int](&intComparator{})
values := []int{6, 5, 2}
for _, v := range values {
maxHeap.Push(v)
}
fmt.Println(maxHeap.Size()) //3
}
# PrintStructure
Print the tree structure of the heap
Signature:
func (h *MaxHeap[T]) PrintStructure()
Example:
package main
import (
"fmt"
heap "github.com/duke-git/lancet/v2/datastructure/heap"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
maxHeap := heap.NewMaxHeap[int](&intComparator{})
values := []int{6, 5, 2, 4, 7, 10, 12, 1, 3, 8, 9, 11}
for _, v := range values {
maxHeap.Push(v)
}
fmt.Println(maxHeap.PrintStructure())
// 12
// 9 11
// 4 8 10 7
// 1 3 5 6 2
}