heap
堆（Heap）是一种完全二叉树。它最大的特性是：每个节点的值都大于等于（或小于等于）其子树节点的值。因此，堆被分成了两类，大顶堆和小顶堆。
堆是一种完全二叉树。它最大的特性是：每个节点的值都大于等于（或小于等于）其子树节点的值。因此，堆被分成了两类，大顶堆和小顶堆。
堆中比较重要的两个操作是插入一个数据和删除堆顶元素。这两个操作都要用到堆化。插入一个数据的时候，我们把新插入的数据放到数组的最后，然后从下往上堆化；
删除堆顶数据的时候，我们把数组中的最后一个元素放到堆顶，然后从上往下堆化。这两个操作时间复杂度都是 O(logn)。
堆的应用
- 优先级队列
- 合并有序小文件
- 高性能定时器
- 求 Top K
- 求中位数
数组中的第 K 个最大元素
build max heap 然后交换堆顶元素和最后一个元素，heapify 前 n-1 个元素，这样堆顶就是第 2 大 的的元素，以此类推，可以找到第 3 大..第 k 大
func findKthLargest(nums []int, k int) int {
for i := (len(nums) - 1) / 2; i >= 0; i-- {
siftDown(nums, i, len(nums))
}
n := len(nums) - 1
for ; k > 1; k-- {
nums[0], nums[n] = nums[n], nums[0]
siftDown(nums, 0, n)
n--
}
return nums[0]
}
func siftDown(a []int, i, n int) {
for {
l, r, larger := i*2+1, i*2+2, i
if l < n && a[l] > a[larger] {
larger = l
}
if r < n && a[r] > a[larger] {
larger = r
}
if larger == i {
break
}
a[i], a[larger] = a[larger], a[i]
i = larger
}
}
剑指 Offer 40. 最小的 k 个数
先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果比堆顶小，则交换位置，然后堆化。
func getLeastNumbers(arr []int, k int) []int {
for i := k / 2; i >= 0; i-- {
siftDown(arr, i, k)
}
for i := k; i < len(arr); i++ {
if arr[i] < arr[0] {
arr[0], arr[i] = arr[i], arr[0]
siftDown(arr, 0, k)
}
}
return arr[0:k]
}
func siftDown(a []int, i, n int) {
for {
l, r, larger := i*2+1, i*2+2, i
if l < n && a[l] > a[larger] {
larger = l
}
if r < n && a[r] > a[larger] {
larger = r
}
if larger == i {
break
}
a[i], a[larger] = a[larger], a[i]
i = larger
}
}
数据流中的第 K 大元素
数据流的中位数
前 K 个高频元素
前 K 个高频单词
合并 K 个排序链表