009.堆结构常见题

前置知识：堆结构和堆排序、比较器

题目1.合并 K 个有序链表 §

题目描述 §

给你一个链表数组，每个链表都已经按升序排列

请你将所有链表合并到一个升序链表中，返回合并后的链表

测试链接 §

• ACM 模式：合并k个已排序的链表
• 核心代码模式：23.合并 K 个升序链表

答案 §

合并 K 个升序链表

题目2.线段最多重合问题 §

题目描述 §

每一个线段都有 start 和 end 两个数据项，表示这条线段在 X 轴上从 start 位置开始到 end 位置结束

给定一批线段，求所有重合区域中最多重合了几个线段，首尾相接的线段不算重合

测试链接 §

线段重合

答案 §

package main
 
import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"sort"
	"strconv"
)
 
const (
	MAXN = 1e4
)
 
var (
	n        int
	arr      = [MAXN][2]int{}
	minHeap  = &MinHeap{}
	heapSize int
)
 
func main() {
	input := bufio.NewScanner(os.Stdin)
	input.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for input.Scan() {
		n, _ = strconv.Atoi(input.Text())
		for i := 0; i < n; i++ {
			input.Scan()
			arr[i][0], _ = strconv.Atoi(input.Text())
			input.Scan()
			arr[i][1], _ = strconv.Atoi(input.Text())
		}
		fmt.Fprintln(out, compute())
	}
    out.Flush()
}
 
func compute() (ans int) {
	// 按 start 排序
	sort.Slice(arr[:n], func(i, j int) bool {
		return arr[i][0] < arr[j][0]
	})
	heapSize = 0
	for i := 0; i < n; i++ {
		// 弹出无法覆盖到的线段
		for heapSize > 0 && minHeap[0] <= arr[i][0] {
			heap.Pop(minHeap)
		}
		heap.Push(minHeap, arr[i][1])
		if heapSize > ans {
			ans = heapSize
		}
	}
    return
}
 
type MinHeap [MAXN]int
 
func (_ *MinHeap) Len() int {
	return heapSize
}
 
func (_ *MinHeap) Less(i, j int) bool {
	return minHeap[i] < minHeap[j]
}
 
func (_ *MinHeap) Swap(i, j int) {
	minHeap[i], minHeap[j] = minHeap[j], minHeap[i]
}
 
func (_ *MinHeap) Push(v any) {
	minHeap[heapSize] = v.(int)
	heapSize++
}
 
func (_ *MinHeap) Pop() (res any) {
	res = minHeap[heapSize-1]
	heapSize--
	return
}

复杂度 §

• 时间复杂度：$O(nlo{g}^n)$
  • 排序 $O(nlo{g}^n)$
  • 堆操作：$lo{g}^n$，每个数进出堆 1 次，共 $n$ 个数
• 空间复杂度：$O(n)$
  • 堆的空间

题目3.让数组整体累加和减半的最少操作次数 §

题目描述 §

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）

请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

测试链接 §

2208.将数组和减半的最少操作次数

思路 §

贪心，优先选最大的数进行减半

注意：数字减少一半不是向下取整，而是保留小数，所以应该用 float 类型

答案 §

func halveArray(nums []int) int {
	n := len(nums)
	maxHeap := make(MaxHeap, n)
	var sum float64 = 0
	count := 0
 
	for i, num := range nums {
		maxHeap[i] = float64(num)
		sum += float64(num)
	}
	sum /= 2
 
	heap.Init(&maxHeap)
	for sum > 0 {
		num := heap.Pop(&maxHeap).(float64) / 2
		sum -= num
		heap.Push(&maxHeap, num)
		count++
	}
 
	return count
}
 
type MaxHeap []float64
 
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.(float64))
}
 
func (h *MaxHeap) Pop() (res any) {
	n := h.Len()
	res = (*h)[n-1]
	*h = (*h)[:n-1]
	return
}

优化：

1. 处理小数选择同时扩大 $2^{20}$，int 比 float 快
2. 堆直接调整，而不是弹出后压入

func halveArray(nums []int) int {
	n := len(nums)
	maxHeap := make(MaxHeap, n)
	sum := 0
	count := 0
 
	for i, num := range nums {
		maxHeap[i] = num << 20
		sum += maxHeap[i]
	}
	sum >>= 1
 
	heap.Init(&maxHeap)
	for sum > 0 {
		maxHeap[0] >>= 1
		sum -= maxHeap[0]
		heap.Fix(&maxHeap, 0)
		count++
	}
 
	return count
}
 
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() (res any) {
	n := h.Len()
	res = (*h)[n-1]
	*h = (*h)[:n-1]
	return
}

复杂度 §

• 时间复杂度：$O(nlo{g}^n)$
  • 堆操作：$lo{g}^n$，即使不取最大值，将每个数都折半也能达到要求，所以取最大值折半次数必定 $\le n$
• 空间复杂度：$O(n)$
  • 堆的空间