堆分为小根堆和大根堆(本质上是一颗完全二叉树)
堆可以干什么?
- 找到一个集合当中的最小值
- 删除一个集合当中的最小值
- 插入一个数
如何调整小根堆或者大根堆?
以小根堆为例子
- down -> 选择这个数和子节点的最小值进行交换
- up -> 选择这个节点与父节点进行交换
如何存储堆?
下标从 1 开始 保证了数组子节点的可行性
选择用数组的形式来存储 1 2 3 4 5 6 7 8
k 的 子节点为 2k 2k+1
如何手写一个堆
- 插入一个数:heap[++size] = x;
- 求集合当中的最小元素:heap[1];
- 删除最小的元素:heap[1] = heap[size]; size ++; down(1) //将末尾的元素覆盖到头节点,数组删除头节点是很麻烦的一件事
- 删除任意一个元素:heap[k] = heap[size]; size ++; down(k); up(k);
- 修改任意一个元素:heap[k] = x;up(x);down(x); 保证 down 和 up 只执行一次
模版题
1 | import java.util.*; |
1 | import java.util.*; |