007.堆结构和堆排序

前置知识：无

堆结构

堆结构是一颗完全二叉树，堆结构可以实现优先级队列

完全二叉树底层存储结构可以用数组

完全二叉树 和数组前缀范围来对应，大小用单独的变量 size 来控制

完全二叉树节点关系与数组索引对应关系：

• i 的父亲节点：(i - 1) >> 1，根节点（索引为 0）的父节点索引是负数，代表不存在
• i 的左孩子：i << 1 + 1
• i 的右孩子：i << 1 + 2，左右孩子的索引要与 size 比较，确定是否在二叉树上（位置有效）

堆的定义

大根堆（小根堆），任何一颗子树都满足父节点的值大于（小于）等于子节点的值，可以清楚整个堆中最大（小）值在堆顶、完全二叉树的根节点、数组的 0 索引处

本节课讲解按照大根堆来讲解，小根堆是同理的

堆的调整

• 向上调整：heapInsert、up
• 向下调整：heapify、down

都很简单易懂，具体代码可以看 这里

heapInsert、heapify 方法的单次调用，时间复杂度 O(logn)，完全二叉树的结构决定的（节点个数为 $n$，则高度为 $lo{g}_2^n$）

Go标准库中的堆

堆排序

建堆

• 从顶到底建堆，时间复杂度 $lo{g}_2^1+lo{g}_2^2+lo{g}_2^3+\cdots +lo{g}_2^n\approx O(n\ast lo{g}^n)$
  • 具体的证明过程比较复杂，这里还可以用 常量增倍分析法 解释
• 从底到顶建堆，时间复杂度 $O(n)$
  • 总代价就是简单的等比数列关系：$\frac{n}{2}\ast 1+\frac{n}{4}\ast 2+\frac{n}{8}\ast 3+\cdots \approx O(n)$

为啥会有差异？简单图解一下

复杂度分析

建好堆之后的调整（排序）阶段，从最大值到最小值依次归位，时间复杂度 $O(n\ast lo{g}^n)$

不管以什么方式 建堆，调整阶段的时间复杂度都是 $O(n\ast lo{g}^n)$，所以整体复杂度也是 $O(n\ast lo{g}^n)$

额外空间复杂度是 $O(1)$，因为堆直接建立在了要排序的数组上，所以没有什么额外空间

代码

测试链接：

• ACM 模式：排序（堆排序）
• 核心代码模式：912.排序数组

package main
 
import (
	"bufio"
	"os"
	"strconv"
)
 
const (
	MAXN = 501
)
 
var (
	n        int
	arr      = [MAXN]int{}
	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())
		if n == 0 {
			continue
		}
		for i := 0; i < n; i++ {
			input.Scan()
			arr[i], _ = strconv.Atoi(input.Text())
		}
		// heapSort1()
		heapSort2()
		out.WriteString(strconv.Itoa(arr[0]))
		for i := 1; i < n; i++ {
			out.WriteByte(' ')
			out.WriteString(strconv.Itoa(arr[i]))
		}
		out.WriteByte('\n')
		out.Flush()
	}
}
 
func heapSort1() {
	heapSize = n
	// 从顶到底建大根堆，O(n*logn)
	for i := 0; i < n; i++ {
		up(i)
	}
	// 依次弹出堆内最大值并排好序，O(n*logn)
	for heapSize > 1 {
		arr[0], arr[heapSize-1] = arr[heapSize-1], arr[0]
		heapSize--
		down(0)
	}
}
 
func heapSort2() {
	heapSize = n
	// 从底到顶建立大根堆，O(n)
	for i := n>>1 - 1; i >= 0; i-- { // n>>1 - 1: 第一个非叶子节点
		down(i)
	}
	// 依次弹出堆内最大值并排好序，O(n*logn)
	for heapSize > 1 {
		arr[0], arr[heapSize-1] = arr[heapSize-1], arr[0]
		heapSize--
		down(0)
	}
}
 
func up(idx int) {
	for {
		parent := (idx - 1) >> 1
		if parent < 0 {
			break
		}
		if arr[parent] >= arr[idx] {
			break
		}
		arr[idx], arr[parent] = arr[parent], arr[idx]
		idx = parent
	}
}
 
func down(idx int) {
	for {
		left := idx<<1 + 1
		maxIdx := idx
		if left < heapSize && arr[left] > arr[maxIdx] {
			maxIdx = left
		}
		if left+1 < heapSize && arr[left+1] > arr[maxIdx] {
			maxIdx = left + 1 // right
		}
		if maxIdx == idx {
			break
		}
		arr[idx], arr[maxIdx] = arr[maxIdx], arr[idx]
		idx = maxIdx
	}
}

常量增倍分析法

数据量为 $n$，复杂度是 $lo{g}^1+lo{g}^2+lo{g}^3+\cdots +lo{g}^n$，如何“化解”这个式子？

用常量增倍分析法！

$lo{g}^1+lo{g}^2+lo{g}^3+\cdots +lo{g}^n$ 扩大到 $\underset{n个}{\underbrace{lo{g}^n+lo{g}^n+lo{g}^n+\cdots +lo{g}^n}}=n\ast lo{g}^n$，即：$n\ast lo{g}^n$ 是它的上限

常量增倍分析法：若数据量为 $2n$ 时，是否以 $n\ast lo{g}^n$ 为下限？

数据量为 $2n$ 时，前 $n$ 个数的高度最高是 $lo{g}^n$，那么后 $n$ 个数的高度一定都是大于 $lo{g}^n$ 的，所以 $n\ast lo{g}^n$ 是它的下限

复杂度是忽略常数项的，所以数据量是 $n$ 还是 $2n$，其复杂度是是一样的

一个算法的复杂度上限和下限都是 $n\ast lo{g}^n$，那么这个算法的复杂度就是 $n\ast lo{g}^n$

再来个例子

计算一个矩阵（n 行 m 列）中有几个子矩阵，其时间复杂度是什么规模的？

选两个点即可确定一个矩形，第一个点：$n\ast m$ 种可能，第二个点：$n\ast m$ 种可能，但是这是有有限种重复情况的：

所以其时间复杂度上限是 $O(n^2\ast m^2)$

常量增倍分析法：若矩形为 $2n\ast 2m$ 时，是否以 $O(n^2\ast m^2)$ 为下限？

是的，因为当第一个点在 A 区域，第二个点在 D 区域时，复杂度为 $O(n^2\ast m^2)$，但第一个点不仅仅能在 A 区域，第二个点也不仅仅能在 D 区域，所以 $O(n^2\ast m^2)$ 是其下限

一个算法的复杂度上限和下限都是 $O(n^2\ast m^2)$，那么这个算法的复杂度就是 $O(n^2\ast m^2)$

备注

注意：堆结构比堆排序有用的多，尤其是和比较器结合之后，后面几节课会重点讲述