[AlgoGo]堆

堆的定义

• 完全二叉树
• 每个节点大于等于子节点

堆的实现

• 存储方式
  堆是一个完全二叉树，完全二叉树适合时候数组存储，因此堆可以用数组实现。

• 堆支持的操作

1. 插入元素
   要点：找到合适的插入位置。
   方法：从下至上堆化，新元素放到尾节点，然后与父节点比较，如果大于父节点就交换，直到小于父节点或交换至根节点。
2. 删除堆顶元素
   要点：删除后保持堆的结构。
   方法：将堆顶元素交换至尾节点，然后进行从上至下的堆化，将堆顶元素与其子节点比较，直到其大于两个子节点。

插入和删除操作的时间复杂度均为O(logn)。

堆排序

1. 建堆
   从n/2（非叶子节点）位置开始倒着到1，对每个节点进行从上至下的建堆过程。
2. 排序
   将堆顶换到末尾，重新堆化，重复n次。

缺点

1. 内存访问不友好，不是连续访问。
2. 相比快速排序，交换次数多。

应用

1. topK问题
2. 优先级队列
3. 中位数