概览
数组我们知道，是一种有序连续的数据结构，随机访问的效率高。之所以随机访问的效率高，就是因为它的每个值都有下标，可以根据下标直接找到我们想要的值。
既然我们已经知道了这种思想，那么我们可以用来做什么呢？
接下来我们就讲讲用数组的思想，或者干脆就直接用数组实现的几种巧妙的思路。
堆排序
首先堆是什么，我理解就是一颗完全二叉树（当然，也有说多叉树也行，但是我没有研究过。）；然后每个节点的值都大于等于它的子节点的值，则为最大堆，反之为最小堆。
接着我们就来看看最小堆是怎么样的一个东西。首先假设有一组数(3、9、2、5、1、6、10、16、7)。那我们初始化成最小堆时是什么个样子呢？
- 首先是按顺序取值，也按顺序存值
- 存入之后判断与父节点的大小
- 如果小于父节点，则交换两者位置
- 循环此步骤
- 否则继续处理下一个数。
- 如果单纯只想要最大最小值的话，到这步其实已经结束了。因为初始化的堆已经保证了根节点就是最大或者最小值
- 如果要继续使堆完全排序，可以将根节点与最后一个节点交换。此时最后一个节点为排序区
- 然后将根节点与子节点比较，若子节点比根节点小，则取最小的一个子节点与根节点交换。交换之后继续与子节点判断，直到无需交换。
- 如此重复4 5步骤，即可得到一个完全排序的堆
总结一下就是：1、初始堆。2、交换根和最后一个未排序的节点，重新调整堆，再交换。如此直到最后就能得到一个完全排序的堆了。
初始化堆
所以我们可以看出，最小堆（或者最大堆）都是父节点和子节点之间的大小关系判断，兄弟节点是没有大小顺序，此时就可以取min或者max值了，如果要完全排序，则可以继续按下面的步骤处理。
完全堆排序
看，经过几轮处理之后，我们就能得到一个完全经过排序的二叉树了。
与数组的关系
说了这么多，那么与数组到底有什么关系呢？其实很简单，这是因为堆的逻辑顺序是一颗二叉树，但是物理顺序却是一个数组。
怎么说呢？我们在存储的时候是将堆从上到下，从左到右平铺到数组中，通过下标来判断父子节点的关系。就以初始化堆之后的二叉树为例，在数组中的存储顺序是：
此时存储形式有2种：
- 下标0存根节点
- 假设当前节点的下标为n，则它的父节点为 (n-1)>>1。它的两个子节点分别为：(n<<1)+1和 (n<<1)+2
- 下标0不存值
- 假设当前节点的下标为n，则它的父节点为 n>>1。它的两个子节点分别为：n<<1和 (n<<1)+1
如此，我们也知道了，可以用数组来存一颗二叉树，而且可以很方便的找到它有关联的父节点甚至祖父节点等。
总结
堆排序，常用于取最大最小值，或者优先级队列和作业调度等。像Java中的PriorityQueue就用到了堆排序，然后JUC中的ScheduledThreadPoolExecutor中也是用到了堆排序。
定时任务调度池的基本实现原理是：
- 将调度任务提取到线程池之前，首先计算下一次需要执行的时间戳，通过时间戳来判断优先级，并将任务存入最小堆中，这样就确保了最先要执行的任务一定在最小堆的顶部，也就是跟节点。
- 然后开一个定时任务，拿堆中第一个任务和当前时间进行比较：
- 如果下一次执行的时间小于等于当前时间，则将该任务从堆中移除，并且投入线程池中执行。
- 如果执行时间大于当前时间，则不处理，因为队列中最先应该执行的任务都还没到时间，其他任务也一定没有到执行时间。
到这里我们的小知识就告一段落了，今天的代码比较少，感兴趣的小伙伴可以根据司机尝试自己实现一下。那我们下期再见了～
标签：下标,活学活用,堆排序,二叉树,数组,排序,节点 From： https://www.cnblogs.com/aischen/p/16976977.html