数据结构 - 二叉堆

Q：Top K问题：从海量数据n中找出前K个数据？

使用排序算法进行全排序，时间复杂度 $O(nlogn)$
使用数据结构二叉堆来解决，时间复杂度 $O(nlogk)$
1.使用小顶堆
2.将前 $k$ 个数放入堆中，然后从 $k+1$ 个数开始，如果大于堆顶元素，replace操作
3.扫描完毕后，堆中剩下的就是最大的前 $k$ 个数

1. 二叉堆（Heap）

(1) 定义

堆（Heap）：是一种树状的数据结构

堆中的元素必须具备 可比较性

任意节点的值总是 $\geq$ 或 $\leq$ 子节点的值
如果任意节点的值总是 $\geq$ 子节点 的值，称为：最大堆、大根堆、大顶堆
如果任意节点的值总是 $\leq$ 子节点 的值，称为：最小堆、小根堆、小顶堆

最大堆_二叉堆、最小堆_二叉堆

2. 二叉堆（Binary Heap）

(1) 定义

二叉堆（Binary Heap）：逻辑结构就是一棵完全二叉树，也叫完全二叉堆
二叉堆的底层一般用数组实现即可

二叉堆

索引 i 的规律（n是元素数量）

如果 $i = 0$ ，它是根节点

如果 $i > 0$ ，它的父节点的索引为 $floor((i - 1) / 2)$

如果 $2i + 1 \leq n - 1$ ，它的左子节点的索引为 $2i + 1$

如果 $2i + 1 > n - 1$ ，它没有左子节点

如果 $2i + 2 \geq n - 1$ ，它的右子节点的索引为 $2i + 2$

如果 $2i + 2 > n - 1$ ，它没有右子节点