堆

堆的应用

重点掌握大顶堆的下沉操作，尤其函数 downAdjust(int[] arr, int parentIndex, int length)的实现。

利用堆求 Top K

“求top K 问题”抽象成两类。一类是针对静态数据集合，也就是说数据集合事先确定，不会再变。另一类是针对静态数据集合，也就是说数据集合事先并不确定，有数据动态地加入到集合中。

针对静态数据，如何在一个包含n个数据的数组中，查找前K大数据呢？

可以维护一个大小为K的大顶堆，顺序遍历数组，从数组中去除数据与堆顶元素比较。如果比堆顶元素大，就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前K大数据了。

遍历数组需要O(n)的时间复杂度，一次堆化操作需要O(logK)的时间复杂度，所以最坏情况下，n个元素都入堆一次，时间复杂度就是O(nlogK)。

针对动态数据求得Top K就是实时Top K。一个数据集合中有两个操作，一个是添加数据，另一个询问当前的前K大数据。

如果每次询问前K大数据，我们都给予当前的数据重新计算的话，那时间复杂度就是O(nlogK)，n表示当前的数据的大小。实际上，可以一直都维护一个K大小的小顶堆，当有数据被添加到集合中是，就拿它与堆顶的元素对比。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理。这样，无论任何时候需要查询当前的前K大数据，都可以立刻发那会给他。

利用堆求中位数

动态的求数据集合的中位数。

这一小节只记录一些概念性的知识，对于具体内容查看极客时间专栏。

如果数据的个数是奇数，把数据从小到大排列，那第 n/2 + 1个数据就是中位数；如果数据是偶数的话，那么处于中间未知的数据有两个，第n/2个和第n/2 + 1个数据，这是随意取一个作为中位数。

99百分位响应时间。如果有n个数据，将数据从小到大排列之后，99百分位数大约就是第n * 99%个数据。

堆的实现

下面实现的是大顶堆。
堆有自我调整的操作，对于二叉堆，有如下几种操作：

• 插入节点。 插入位置总是位于二叉树的最后一个位置，然后作为childIndex和parentIndex比较大小。
• 删除节点。 总是删除堆顶的元素，然后把最后一个位置的元素放在堆顶，然后向下调整位置。
• 构建二叉树。本质上就是让所以非叶子节点依次下沉。

下面证明，对于完全二叉树来说，下标从n/2 + 1 到 n的节点都是叶子节点？ 使用反证法证明即可：

使用数组存储表示完全二叉树时，从 数组下标为1开始存储数据，数组下标为i的节点，左子节点为2i, 右子节点为2i + 1. 这个结论很重要（可以用数学归纳法证明)，将此结论记为『原理1』，以下证明会用到这个原理。

如果下标为n/2 + 1的节点不是叶子节点，即它存在子节点，按照『原理1』，它的左子节点为：2(n/2 + 1) = n + 2，大家明显可以看出，这个数字已经大于n + 1，超出了实现完全二叉树所用数组的大小（数组下标从1开始记录数据，对于n个节点来说，数组大小是n + 1），左子节点都已经超出了数组容量，更何况右子节点。以此类推，很容易得出：下标大于n/2 + 1的节点肯定都是也叶子节点了，故而得出结论：对于完全二叉树来说，下标从n/2 + 1 到 n的节点都是叶子节点

数组下标为0开始存储数据，数组下标为i的节点，左子节点为2i + 1, 右子节点为2i + 2。下标为n/2 到 n - 1的节点都是叶子节点，那么最后一个非叶子节点是n/2 - 1

/**
 * @description: 二叉堆
 * @author: rhsphere
 * @since: 2019-07-04 16:30 by jdk 1.8
 */
public class Heap {
	//上浮操作
	public static void upAdjust(int[] arr) {
		int childIndex = arr.length - 1;  //孩子节点
		int parentIndex = (childIndex - 1) / 2; 
		//保存插入的叶子节点值，用于最后的赋值
		int tmp = arr[childIndex];

		while (childIndex > 0 && tmp > arr[parentIndex]) {
			arr[childIndex] = arr[parentIndex];
			childIndex = parentIndex;
			parentIndex = (parentIndex - 1) / 2;
		}
		arr[childIndex] = tmp;
	}

	/**
	 * 下沉调整
	 * @param arr          待调整的堆
	 * @param parentIndex  要下沉的父节点
	 * @param length       堆的有效大小
	 */
	public static void downAdjust(int[] arr, int parentIndex, int length) {
		//保存父节点的值，用于最后赋值
		int tmp = arr[parentIndex];
		//左孩子节点
		int childIndex = 2 * parentIndex + 1;

		while (childIndex < length) {
			//如果有右孩子节点，且右孩子的值大于左孩子的值，则定位到右孩子
			if (childIndex + 1 < length &&
				arr[childIndex + 1] > arr[childIndex]) {
				childIndex++;
			}
			//如果父节点大于等于，任何一个孩子的值，直接跳出
			if (tmp >= arr[childIndex])
				break;

			//给父节点单向赋值，最后的一个坑填上tmp即可
			arr[parentIndex] = arr[childIndex];
			parentIndex = childIndex;         //父节点的下标
			childIndex = 2 * parentIndex + 1;  //左孩子节点下标
		}
		//最后一个坑位，填上tmp
		arr[parentIndex] = tmp;
	}

	public staitc void buildIndex(int[] arr) {
		//从最后一个非叶子节点开始，依次下沉
		for (int i = arr.length/2 - 1; i >= 0; i--)
			downAdjust(arr, i, arr.length);
	}
}

---