Heap
题目
heap的特性
用array来实现。对于index为i的元素来说
- parent 是 i - 1 / 2
- left child 是 2 * i + 1
- right child 是 2 * i + 2
sift up
push的时候的步骤
- append到array的最后
- 一直与parent比较sift up，直到满足heap的性质
sift down
pop的时候的步骤
- 将root和array的末尾swap
- 删除末尾元素
- 对root对sift down
解题方法
- 一般需要快速找到max, min的
- 需要快速比较多个值并且取最大最小值的
- 找出top k的东西的