Java集合与数据结构——优先级队列（堆）

、二叉树的次序存储

1.堆的存储方法

  使用数组保存二叉树结构，方法即将二叉树用层序遍历方法放入数组中。

  一般只适合表明彻底二叉树，因为非彻底二叉树会有空间的糟蹋。

这种方法的主要用法就是堆的表明。




2.下标关系

已知 双亲 (parent) 的下标，则：


左孩子(left)下标 = 2 * parent + 1;

右孩子(right)下标 = 2 * parent + 2;


已知孩子（不区别左右）(child)下标，则：


双亲(parent)下标 = (child - 1) / 2;


二、堆(heap)

1.概念

1.堆逻辑上是一棵彻底二叉树

2.堆物理上是保存在数组中

3.满意任意结点的值都大于其子树中结点的值，叫做大堆，或许大根堆，或许最大堆

4.反之，则是小堆，或许小根堆，或许最小堆

5.堆的基本作用是，快速找集合中的最值


2.大/小 根堆

2.1小根堆


每棵树的根节点都是小于孩子节点，此时这棵树就叫做小根堆


2.2大根堆


每棵树的根节点都是大于孩子节点的，此时这棵树就叫做大根堆

  咱们在说 巨细根堆 时，只说了 根节点比孩子节点大，没有说 左右孩子节点谁比谁大、谁比谁小.

所以得出结论

不管是 大根堆、仍是小根堆，左右孩子的巨细关系是不确定的，咱们只能确定根节点和孩子节点的关系.


3.建堆操作

  下面咱们给出一个数组，这个数组逻辑上能够看做一颗彻底二叉树，但是还不是一个堆，现在咱们通过算法，把它构建成一个堆。


  根节点左右子树不是堆，咱们怎么调整呢？这里咱们从倒数的第一个非叶子节点的子树开端调整，一向调整到根节点的树，就能够调整成堆。


将一个二叉树 调整为一个 大根堆





这棵二叉树调整为 大根堆 必须将 每颗子树都调整为大根堆.


3.1向下调整

思想 步骤：

parent —> 根节点下标

child —> 孩子节点下标


1.从最终一棵子树进行调整.

2.每颗子树从根节点向下调整，假如左右孩子节点的最大值比这个根节点大，那么值互换，然后 parent 指向 child ,child = 2* parent + 1， 继续向下调整，直到 下标child 超出二叉树 规模.

3.重复第二步的操作，遍历每一颗子树，直到所有子树全部遍历完结.


代码实现：





咱们对这个代码进行测验



测验堆中的结果：


时间复杂度分析：


  粗略预算，能够认为是在循环中执行向下调整，为 O(n * log(n))（了解）实际上是 O(n)


堆排序中建堆过程时间复杂度O(n)怎么来的？




4.入队操作

步骤

1.判断是否满容

2.在数组的最终插入元素

3.调整为 大/小 根堆


在这几个步骤中，前两步咱们都能够完结 ，第三步咱们要注意：


使用 向上调整 调整为大/ 小根堆


之前咱们介绍了 向下调整

这次咱们说的是向上调整，与之前向上调整的思路十分相似~~

咱们来说一下 向上调整的思路


4.1向上调整




4.2push 入队的完好代码展示




5.出队操作

  为了避免破坏堆的结构，删去时并不是直接将堆顶元素删去，而是用数组的最终一个元素与堆顶元素交流，然后通过向下调整方法重新调整成堆.


思路：


1.交流 数组首尾元素

2.usedSize- -,删去最终的元素

3.使用向下调整 ，调整为大/小 根堆


5.1pop 出队代码彻底展示



6.检查堆顶元素

回来 下标为0的数组元素.回来堆顶元素.





现在咱们来看一个 堆的 使用


7.TOK 问题

咱们在这里 提出一个问题：


在一千万个数据中找到 前 10个最大的 数据,请问如何查找

咱们有 几个想法


1.基本反应，给1000万个数据排序，取10个最大 的，咱们直接 Arrays.sort () ;

  这种排序方法当然也不是不能够，只不过时间复杂度非常大，在面试中写出这样的排序思路会落得劣势.


2.将这1000个数据 建成一个大堆，每次将最大的取出，然后调整，取出10个即可.

  这种方法的缺陷则是， 堆太大了，咱们建立的堆也会是 1000万，假如这个数据更大，那么堆也会更大，每次调整的复杂度也很大.


3.建立一个巨细为 K 的小堆.




以上面这个数组为例，找出这组数据中的前三个最大的元素.


3.1 将当时数据的前三个 建立为小堆

3.2 遍历剩余的元素，顺次和堆顶元素进行比较. 假如当时 i 下标元素 比堆顶元素大，就把i下标入队.



  堆顶元素一定是最小的，每次都与堆顶元素进行比较，每次都将最小的那个除掉，最终遍历完，剩余的就是 最大的几个数据了嘛~

根据上面的这个 思路，咱们同理能够解决许多相似的问题