java中实现热门搜索的逻辑_Java编程的逻辑（45）-神奇的堆前⾯⼏节介绍了Java中的基本容器类，每个容器类背后都有⼀种数据结构，ArrayList是动态数组，LinkedList是链
表，HashMap/HashSet是哈希表，TreeMap/TreeSet是红⿊树，本节介绍另⼀种数据结构 - 堆。
引⼊堆
之前我们提到过堆，那⾥，堆指的是内存中的区域，保存动态分配的对象，与栈相对应。这⾥的堆是⼀种数据结构，与内存区域和分配⽆关。
堆是什么结构呢？这个我们待会再细看。我们先来说明，堆有什么⽤？为什么要介绍它？
堆可以⾮常⾼效⽅便的解决很多问题，⽐如说：
优先级队列，我们之前介绍的队列实现类LinkedList是按添加顺序排队的，但现实中，经常需要按优先级来，每次都应该处理当前队列中优先级最⾼的，⾼优先级的，即使来得晚，也应该被优先处理。
求前K个最⼤的元素，元素个数不确定，数据量可能很⼤，甚⾄源源不断到来，但需要知道到⽬前为⽌的最⼤的前K个元素。这个问题的变体有：求前K个最⼩的元素，求第K个最⼤的，求第K个最⼩的。
求中值元素，中值不是平均值，⽽是排序后中间那个元素的值，同样，数据量可能很⼤，甚⾄源源不断到来。
堆还可以实现排序，称之为堆排序，不过有⽐它更好的排序算法，所以，我们就不介绍其在排序中的应⽤了。
Java容器中有⼀个类PriorityQueue，就表⽰优先级队列，它实现了堆，下节我们会详细介绍。关于后⾯两个问题，它们是如何使⽤堆⾼效解决的，我们会在接下来的⼏节中⽤代码实现并详细解释。
说了这么多好处，堆到底是什么呢？
堆的概念
完全⼆叉树
堆⾸先是⼀颗⼆叉树，但它是完全⼆叉树。什么是完全⼆叉树呢？我们先来看另⼀个相似的概念，满⼆叉树。
满⼆叉树是指，除了最后⼀层外，每个节点都有两个孩⼦，⽽最后⼀层都是叶⼦节点，都没有孩⼦。⽐如，下图两个⼆叉树都是满⼆叉树。
满⼆叉树⼀定是完全⼆叉树，但完全⼆叉树不要求最后⼀层是满的，但如果不满，则要求所有节点必须集中在最左边，从左到右是连续的，中间不能有空的。⽐如说，下⾯⼏个⼆叉树都是完全⼆叉树：
⽽下⾯的这⼏个则都不是完全⼆叉树：
编号与数组存储
在完全⼆叉树中，可以给每个节点⼀个编号，编号从1开始连续递增，从上到下，从左到右，如下图所⽰：
完全⼆叉树有⼀个重要的特点，给定任意⼀个节点，可以根据其编号直接快速计算出其⽗节点和孩⼦节点编号，如果编号为i，则⽗节点编号即为i/2，左孩⼦编号即为2*i，右孩⼦编号即为2*i+1。⽐如，对于5号节点，⽗节点为5/2即2，左孩⼦为2*5即10，右孩⼦为2*5+1即11。
这个特点为什么重要呢？它使得逻辑概念上的⼆叉树可以⽅便的存储到数组中，数组中的元素索引就对应节点的编号，树中的⽗⼦关系通过其索引关系隐含维持，不需要单独保持。⽐如说，上图中的逻辑⼆叉树，保存到数组中，其结构为：
⽗⼦关系是隐含的，⽐如对于第5个元素13，其⽗节点就是第2个元素15，左孩⼦就是第10个元素7，右孩⼦就是第11个元素4。
这种存储⼆叉树的⽅法与之前介绍的TreeMap是不⼀样的，在TreeMap中，有⼀个单独的内部类Entry，Entry有三个引⽤，分别指向⽗节点、左孩⼦、右孩⼦。
二叉树的基本性质使⽤数组存储，优点是很明显的，节省空间，访问效率⾼。
最⼤堆/最⼩堆
堆逻辑概念上是⼀颗完全⼆叉树，⽽物理存储上使⽤数组，除了这两点，堆还有⼀定的顺序要求。
之前介绍过排序⼆叉树，排序⼆叉树是完全有序的，每个节点都有确定的前驱和后继，⽽且不能有重复元素。
与排序⼆叉树不同，在堆中，可以有重复元素，元素间不是完全有序的，但对于⽗⼦节点之间，有⼀定
的顺序要求，根据顺序分为两种堆，⼀种是最⼤堆，另⼀种是最⼩堆。
最⼤堆是指，每个节点都不⼤于其⽗节点。这样，对每个⽗节点，⼀定不⼩于其所有孩⼦节点，⽽根节点就是所有节点中最⼤的，对每个⼦树，⼦树的根也是⼦树所有节点中最⼤的。
最⼩堆与最⼤堆正好相反，每个节点都不⼩于其⽗节点。这样，对每个⽗节点，⼀定不⼤于其所有孩⼦节点，⽽根节点就是所有节点中最⼩的，对每个⼦树，⼦树的根也是⼦树所有节点中最⼩的。
我们看下图⽰：
堆概念总结
总结来说，逻辑概念上，堆是完全⼆叉树，⽗⼦节点间有特定顺序，分为最⼤堆和最⼩堆，最⼤堆根是最⼤的，最⼩堆根是最⼩的，堆使⽤数组进⾏物理存储。
这个数据结构为什么就可以⾼效的解决之前我们说的问题呢？在回答之前，我们需要先看下，如何在堆上进⾏数据的基本操作，在操作过程中，如何保持堆的属性不变。
堆的算法
下⾯，我们来看下，如何在堆上进⾏数据的基本操作。最⼤堆和最⼩堆的算法是类似的，我们以最⼩堆来说明。先来看如何添加元素。
添加元素
如果堆为空，则直接添加⼀个根就⾏了。我们假定已经有⼀个堆了，要在其中添加元素。基本步骤为：
添加元素到最后位置。
与⽗节点⽐较，如果⼤于等于⽗节点，则满⾜堆的性质，结束，否则与⽗节点进⾏交换，然后再与⽗节点⽐较和交换，直到⽗节点为空或者⼤于等于⽗节点。
我们来看个例⼦。下⾯是初始结构：
添加元素3，第⼀步后，结构变为：
3⼩于⽗节点8，不满⾜最⼩堆的性质，所以与⽗节点交换，会变为：
交换后，3还是⼩于⽗节点6，所以继续交换，会变为：
交换后，3还是⼩于⽗节点，也是根节点4，继续交换，变为：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。