堆的基本原理
摘要
- Priority Queue和堆的联系和区别
- 堆的基本原理
- 堆的基本操作Sift Up和Sift Down
- 堆的增删查改
- 堆的初始化 Heapify
- 堆排序
时间复杂度
- add(element) => O(logn)
- pop() 取最顶上的元素 => O(logn)
- peak() min/max => O(1)
结构
堆的结构是从上到下，从左到右的
minHeap: 所有父亲节点都比儿子节点小
基本操作
4
/ \
5 6
/ \
8 7
加入 3
4
/ \
5 6
/ \ /
8 7 3
shift up
3
/ \
5 4
/ \ /
8 7 6
树有多高，就会最多调整几次 O(logn)
pop() 取出 3，用最后的值覆盖
6
/ \
5 4
/ \
8 7
用两个儿子中较小的做调整，最多调整也是高度，O(logn)
4
/ \
5 6
/ \
8 7
存储
Array index=0 存储总数量
0 1 2 3 4 5 6 7
7 1 2 3 4 5 6 7
1
/ \
2 3
/ \ / \
4 5 6 7
3 父亲节点 3/2 = 1
3 左儿子节点 3*2 = 6
3 右儿子节点 3*2+1 = 7
130 · 堆化
时间复杂度为 O(n)，使用的是 siftdown
之所以是 O(n) 是因为从第 N/2 个位置开始往下 siftdown，那么就有大约 N/4 个数在 siftdown 中最多交换 1 次，N/8 个数最多交换 2 次，N/16 个数最多交换 3 次。
// Heapify transforms the array into a min-heap.
func Heapify(nums []int) {
for i := len(nums) / 2; i >= 0; i-- {
siftDown(nums, i)
}
}
// siftDown adjusts the elements to maintain the min-heap property.
func siftDown(nums []int, index int) {
n := len(nums)
for index < n {
left := index*2 + 1
right := index*2 + 2
minIndex := index
if left < n && nums[left] < nums[minIndex] {
minIndex = left
}
if right < n && nums[right] < nums[minIndex] {
minIndex = right
}
if minIndex == index {
break
}
nums[minIndex], nums[index] = nums[index], nums[minIndex]
index = minIndex
}
}
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。