# Heap
堆，切片实现的二叉堆数据结构。
# 源码
# 用法
import (
heap "github.com/duke-git/lancet/v2/datastructure/heap"
)
# API 文档
# 1. MaxHeap
MaxHeap 是通过 slice 实现的二叉堆树，根节点的 key 既大于等于左子树的 key 值且大于等于右子树的 key 值。
# NewMaxHeap
返回NewMaxHeap指针实例
函数签名:
type MaxHeap[T any] struct {
data []T
comparator lancetconstraints.Comparator
}
func NewMaxHeap[T any](comparator lancetconstraints.Comparator) *MaxHeap[T]
例子:
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
向堆中插入数据
函数签名:
func (h *MaxHeap[T]) Push(value T)
例子:
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
返回堆中最大值并将其从堆中删除，如果堆为空，返回零值并返回false
函数签名:
func (h *MaxHeap[T]) Pop() (T, bool)
例子:
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
返回堆中最大值，如果堆为空，返回零值并返回false
函数签名:
func (h *MaxHeap[T]) Peek() (T, bool)
例子:
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
返回堆中全部元素的切片
函数签名:
func (h *MaxHeap[T]) Data() []T
例子:
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
返回堆中元素的数量
函数签名:
func (h *MaxHeap[T]) Size() int
例子:
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
打印堆的树形结构
函数签名:
func (h *MaxHeap[T]) PrintStructure()
例子:
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
}