（大根堆）实现#

// i节点破坏了规则，对以i为根的子树进行调整
// 自顶向下调整
// 不一定调整到叶子
adjust(arr, i, len) {
	l := 2 * i
	r := 2 * i + 1
	if l > len { return } //没有子树
	k := if r <= len and arr[r] > arr[l] { r } else { l }
	if arr[i] < arr[k] {
		swap(arr[i], arr[k])
		adjust(arr,k,len)
	}
	
}
// 0号元素不适用
// 待建立堆的范围是 (0,len]
// 自底向上建堆
// 复杂度O(n)
make_heap(arr,len) {
	 for i := len/2; i > 0; i-- {
		adjust(arr,i,len) 
	 }
}

// 入堆
// 自底向上入堆，不一定调整到根
push(arr,len,val) {
	// 插入后新的末尾位置是len+1
	arr[len+1] = val
	for i := len + 1; i > 1；i >> 1 {
		if arr[i] <= arr[i>>1] { break }
		swap(arr[i], arr[i>>1])
	}
}

// 出堆
// 自顶向下调整
// 不一定调整到叶子
pop(arr,len) {
	val := arr[1]
	arr[1] = arr[len]
	adjust(arr,1,len-1)
}

heap_sort(arr,len) {
	make_heap(arr,len)
	for i := len; i > 0; i-- {
		val = pop(arr,i)
		arr[i] = val
	} 
}

应用#

• 优先队列
• 在大量数据中选出k个最小值
  • 对前k个值建立大根堆
  • 对后面的值如果大于堆顶抛弃，否则代替堆顶并自顶向下调整成新堆
  • 遍历完数据后依次出堆得到k个最小值