前置条件
golang 优先队列几种构建方式,使用比起其他语言稍微有些复杂
- 简单构建方式
// 最小堆 s[0] 为堆顶 heap.Fix(&h,0) 可以从下标位置重新调整堆
type small []int
func (s small)Less(i,j int)bool{
return s[i]<s[j]
}
func (s small)Swap(i,j int){
s[i],s[j] = s[j],s[i]
}
func (s small)Len()int{
return len(s)
}
func (s *small)Push(x interface{}){
tmp:=x.(int)
*s = append(*s,tmp)
}
// 使用时 s:=new(small)
看到另外一种构建方式
func main(){
nums:=[]int{1,6,4,8,2,7,2,4}
h:=hp{}
for _,v:=range nums{
heap.Push(&h,v)
}
for h.Len()!=0{
fmt.Printf("%d ",heap.Pop(&h))
}
// 输出为 8 7 6 4 4 2 2 1
}
type hp struct{
sort.IntSlice //底层是[]int{} 并且已经实现了 Len Less默认升序 Swap 所以作为优先队列只需要实现 Push和Pop即可
//type IntSlice []int
}
//需要改降序则实现Less
func (h hp)Less(i ,j int)bool{
return h.IntSlice[i]>h.IntSlice[j]
}
func (h *hp) Push(x interface{}) { h.IntSlice = append(h.IntSlice, x.(int)) }
func (h *hp) Pop() interface{} {
old := h.IntSlice
n := len(old)
x := old[n-1]
h.IntSlice = old[0 : n-1]
return x
}
6178. 将区间分为最少组数
- 简单构建优先队列
func minGroups(intervals [][]int) int {
if len(intervals)==0{
return 0
}
//按照前面一个位置进行排序,相等按照后面的升序
sort.Slice(intervals,func(i,j int)bool{
if intervals[i][0]!=intervals[j][0]{
return intervals[i][0]<intervals[j][0]
}
return intervals[i][1]>intervals[j][1]
})
//注意使用时用Heap.Push(&h,val) Heap,Pop(&h) 关于绑定interface问题参考eggo
s:=new(small)
for i:=0;i<len(intervals);i++{
if s.Len()==0||intervals[i][0]<=(*s)[0]{ //当前小于等于堆顶,则需要重新开一个组
heap.Push(s,intervals[i][1])
}else{
(*s)[0] = intervals[i][1] //可以放置,之前替换之前组的末尾数字,重新再平衡,或者 Heap.Pop() 后 Heap.Push()
heap.Fix(s,0)
}
}
return s.Len()
}
// 最小堆 s[0] 为堆顶 heap.Fix(&h,0) 可以从下标位置重新调整堆
type small []int
func (s small)Less(i,j int)bool{
return s[i]<s[j]
}
func (s small)Swap(i,j int){
s[i],s[j] = s[j],s[i]
}
func (s small)Len()int{
return len(s)
}
func (s *small)Push(x interface{}){
tmp:=x.(int)
*s = append(*s,tmp)
}
func (s *small)Pop()interface{}{
x:=(*s)[len(*s)-1]
(*s) = (*s)[:len(*s)-1]
return x
}