Golang实现最大堆/最小堆

Golang实现最大堆/最小堆

参考： https://yangjiahao106.github.io/2019/01/15/golang-%E6%9C%80%E5%A4%A7%E5%A0%86%E5%92%8C%E6%9C%80%E5%B0%8F%E5%A0%86/
https://studygolang.com/articles/24288

方法一

此方法就是比较传统、常见的方法，下面来构建一个最小堆：

type Heap struct {
	Size int
	Elems []int
}

func NewHead(maxSize int) *Heap {
	//minHead := new(Heap)
	//minHead.Elems = make([]int, maxSize, maxSize)
	//return minHead
	minHead := Heap{Size: -1, Elems: make([]int, maxSize, maxSize)}
	return &minHead
}

func (h *Heap) Push(x int)  {
	if h.Size == len(h.Elems) - 1 {
		return
	}
	
	h.Size++
	i := h.Size
	// 与父节点进行比较，如果小于父节点，则向上冒泡；否则，停止；
	for i > 0 {
		parent := (i - 1) / 2
		if h.Elems[parent] <= x {
			break
		}
		h.Elems[i] = h.Elems[parent]
		i = parent
	}
	h.Elems[i] = x
}

func (h *Heap) Pop() int {
	if h.Size < 0 {
		return math.MinInt32
	}

	ret := h.Elems[0]
	// 将最后一个节点提到根节点，然后向下交换
	x := h.Elems[h.Size]
	i := 0
	for {
		l := 2*i + 1
		r := 2*i + 2

		if l >= h.Size {
			break
		}

		if r < h.Size && h.Elems[l] > h.Elems[r] {
			l = r
		}

		if x <= h.Elems[l] {
			break
		}

		h.Elems[i] = h.Elems[l]
		i = l
	}
	h.Size--
	h.Elems[i] = x
	return ret
}

测试：

func main() {
	minHead := NewHead(10)
	minHead.Push(2)
	minHead.Push(7)
	minHead.Push(5)
	minHead.Push(5)
	minHead.Push(4)
	minHead.Push(8)
	minHead.Push(8)
	minHead.Push(8)
	minHead.Push(8)
	minHead.Push(12)
	minHead.Push(20)

	k := minHead.Pop()
	for k != math.MinInt32 {
		fmt.Println(k)
		k = minHead.Pop()
	}
}

/* output:
		2
		4
		5
		5
		7
		8
		8
		8
		8
		12
*/

一些其他的操作，可以在此基础进行扩充。

方法二

container/heapheapheapheap

type Interface interface {
	sort.Interface
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}

// sort.Interface
type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

Less(i, j int) boolsort.go

if data.Less(m1, m0) {
	data.Swap(m1, m0)
}

Less()data[i]data[j]

type minHeap []int

func (h minHeap) Len() int {
	return len(h)
}

// 这里实现了小根堆，如果想要实现大根堆可以改为 h[i] > h[j]
func (h minHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h *minHeap) Swap(i, j int)  {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *minHeap) Push(x interface{})  {
	*h = append(*h, x.(int))
}

func (h *minHeap) Pop() interface{} {
	res := (*h)[len(*h) - 1]
	*h = (*h)[:len(*h) - 1]
	return res
}

测试：

func main() {
	h := make(minHeap, 0)
	heap.Init(&h)

	heap.Push(&h, 2)
	heap.Push(&h, 7)
	heap.Push(&h, 5)
	heap.Push(&h, 5)
	heap.Push(&h, 4)
	heap.Push(&h, 6)

	for len(h) != 0 {
		fmt.Println(heap.Pop(&h))
	}
}

/*output:
		2
		4
		5
		5
		6
		7
*/