首页 计算机科学 算法训练 2023

# 堆

# 概念与特征

堆是将一组数据按照完全二叉树的存储顺序，将数据存储在一个一维数组中的结构。堆有两种结构，一种称为大顶堆，一种称为小顶堆

小顶堆：任意节点的值均小于等于它的左右孩子，并且最小的值位于堆顶，即根节点处。

大顶堆：任意节点的值均大于等于它的左右孩子，并且最大的值位于堆顶，即根节点处。

有些地方也叫大根堆、小根堆，或者最大堆、最小堆都一个意思。

优先队列：说到底还是一种队列，他的工作就是 poll ()/peek () 出队列中最大 / 最小的那个元素，所以叫带有优先级的队列。能够实现优先功能的策略不一定只有堆，例如二项堆、平衡树、线段树、C++ 里会用二进制分组的 vector 来实现一个优先队列。

堆：堆是一个很大的概念 他并不一定是完全二叉树。我们之前用完全二叉树是因为这个很容易被数组储存，但是除了这种二叉堆之外，我们还有二项堆、斐波那契堆、这种堆就不属于二叉树。

golang 堆可以借助 container/heap 去实现

container 源码解析：https://blog.twelveeee.top/2023/Go/Lib/sort_and_container/#container

import "container/heap"
type IntHeap []int
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
	x := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return x
}
func (h *IntHeap) Len() int {
	return len(*h)
}
func (h *IntHeap) Less(i, j int) bool {
	return (*h)[i] < (*h)[j]
}
func (h *IntHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}
func newIntHeap() *IntHeap {
	h := &IntHeap{}
	heap.Init(h)
	return h
}
func TestGoHeap(t *testing.T) {
	h := newIntHeap()
	heap.Push(h, 5)
	heap.Push(h, 4)
	heap.Push(h, 1)
	heap.Push(h, 3)
	heap.Push(h, 2)
	if h.Len() != 5 {
		t.Error("Heap.Len() != 5")
	}
	for h.Len() > 0 {
		t.Log(heap.Pop(h))
	}
}
# 普通算法题
# 1. 合并 K 个升序链表
https://leetcode.cn/problems/merge-k-sorted-lists/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/14_Heap/level_2/topic_1.go
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
func mergeKLists(lists []*ListNode) *ListNode {
	h := &ListNodeHeap{}
	heap.Init(h)
	for _, node := range lists {
		if node != nil {
			heap.Push(h, node)
		}
	}
	dummyHead := &ListNode{}
	curr := dummyHead
	for len(*h) > 0 {
		node := heap.Pop(h).(*ListNode)
		if node.Next != nil {
			heap.Push(h, node.Next)
		}
		curr.Next = node
		curr = curr.Next
	}
	return dummyHead.Next
}
type ListNodeHeap []*ListNode
func (h *ListNodeHeap) Len() int           { return len(*h) }
func (h *ListNodeHeap) Less(i, j int) bool { return (*h)[i].Val < (*h)[j].Val }
func (h *ListNodeHeap) Swap(i, j int)      { (*h)[i], (*h)[j] = (*h)[j], (*h)[i] }
func (h *ListNodeHeap) Push(val any)       { *h = append(*h, val.(*ListNode)) }
func (h *ListNodeHeap) Pop() any           { x := (*h)[len(*h)-1]; (*h) = (*h)[:len(*h)-1]; return x }
# 中位数问题
两个堆，一个大顶堆，一个小顶堆。
# 2. 数据流的中位数
https://leetcode.cn/problems/find-median-from-data-stream/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/14_Heap/level_3/topic_1.go
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。
type MedianFinder struct {
	maxHeap *MaxHeap
	minHeap *MinHeap
}
func Constructor() MedianFinder {
	maxHeap, minHeap := &MaxHeap{}, &MinHeap{}
	heap.Init(maxHeap)
	heap.Init(minHeap)
	return MedianFinder{maxHeap, minHeap}
}
func (this *MedianFinder) AddNum(num int) {
	heap.Push(this.minHeap, num)
	heap.Push(this.maxHeap, heap.Pop(this.minHeap))
	for this.minHeap.Len() < this.maxHeap.Len() {
		heap.Push(this.minHeap, heap.Pop(this.maxHeap))
	}
}
func (this *MedianFinder) FindMedian() float64 {
	if this.minHeap.Len() > this.maxHeap.Len() {
		return float64(this.minHeap.Top())
	}
	return float64(this.minHeap.Top()+this.maxHeap.Top()) / 2
}
/**
 * Your MedianFinder object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(num);
 * param_2 := obj.FindMedian();
 */
type MinHeap []int
func (h *MinHeap) Len() int           { return len(*h) }
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(val any)       { (*h) = append((*h), val.(int)) }
func (h *MinHeap) Pop() any {
	val := (*h)[len(*h)-1]
	(*h) = (*h)[:len(*h)-1]
	return val
}
func (h *MinHeap) Top() int { return (*h)[0] }
type MaxHeap []int
func (h *MaxHeap) Len() int           { return len(*h) }
func (h *MaxHeap) Less(i, j int) bool { return (*h)[i] > (*h)[j] }
func (h *MaxHeap) Swap(i, j int)      { (*h)[i], (*h)[j] = (*h)[j], (*h)[i] }
func (h *MaxHeap) Push(val any)       { (*h) = append((*h), val.(int)) }
func (h *MaxHeap) Pop() any           { val := (*h)[len(*h)-1]; (*h) = (*h)[:len(*h)-1]; return val }
func (h *MaxHeap) Top() int           { return (*h)[0] }
# 第 k 大元素
第 k 大元素，使用小顶堆，保证栈顶元素是最小的元素。
如果堆的长度超过 k，则弹出栈顶元素，直到长度小于等于 k。
剩下的栈顶元素就是当前第 K 大的元素。
反之，第 k 小元素使用大顶堆。
# 3. 第 k 大元素
import (
	"container/heap"
	"fmt"
)
type MinHeap []int
func (h MinHeap) Len() int {
	return len(h)
}
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{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
func findKthLargest(nums []int, k int) int {
	if len(nums) < k {
		return -1
	}
	// 初始化最小堆
	h := &MinHeap{}
	heap.Init(h)
	// 维护堆的大小为 K
	for _, num := range nums {
		heap.Push(h, num)
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	// 堆顶元素即为第 K 大的元素
	return (*h)[0]
}
func main() {
	nums := []int{3, 1, 4, 2, 5, 8, 7, 6}
	k := 3
	kthLargest := findKthLargest(nums, k)
	fmt.Printf("第%d大的元素为：%d\n", k, kthLargest) // 输出：第 3 大的元素为：6
}
 
-->