网站建设吉金手指排名12,免费下载网站有哪些,莱州网站开发,惠州市建设厅网站目录
堆的概念#xff1a;
堆的性质#xff1a;
堆的存储方式#xff1a;
堆的创建 #xff1a;
堆的调整#xff1a;
向下调整#xff1a;
向上调整#xff1a;
堆的创建#xff1a;
建堆的时间复杂度#xff1a; 向下调整#xff1a;
向上调整#xff…目录
堆的概念
堆的性质
堆的存储方式
堆的创建
堆的调整
向下调整
向上调整
堆的创建
建堆的时间复杂度 向下调整
向上调整
堆的插入与删除 堆的插入
堆的删除
堆的应用
1.PriorityQueue的实现
2.堆排序
3.Top-k问题
结语 堆的概念
如果有一个关键码的集合K {k0k1 k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储 在一 个一维数组中并满足Ki K2i1 且 Ki K2i2) i 012…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。
堆的性质 1堆中某个节点的值总是不大于大根堆或不小于小根堆其父节点的值。 2堆总是一棵完全二叉树。 具体如下图。 堆的存储方式 从堆的概念可知堆是一棵完全二叉树因此可以层序的规则采用顺序的方式来高效存储。
注意对于非完全二叉树则不适合使用顺序方式进行存储因为为了能够还原二叉树空间中必须要存储空节点就会导致空间利用率比较低。
将元素存储到数组中后可以根据二叉树章节的性质对树进行还原。假设i为节点在数组中的下标则有 1如果i为0则i表示的节点为根节点否则i节点的双亲节点为 (i - 1)/2. 2如果2 * i 1 小于节点个数则节点i的左孩子下标为2 * i 1否则没有左孩子。 3如果2 * i 2 小于节点个数则节点i的右孩子下标为2 * i 2否则没有右孩子。 堆的创建
为了使文章可读性更高下面给出测试堆类的基本代码下面文章给出的代码均围绕这上面来。 elem是一个类里面的数组方便后序操作 usedSize是记录数组里面有多少个元素不是数组容量 TestHeap构造方法为了简便把数组容量设为10大小可以自己调整 initElem初始化 public class TestHeap {public int[] elem;public int usedSize;public TestHeap(){elem new int[10];}public void initElem(int[] array){for(int i 0;i array.length;i){elem[i] array[i];usedSize;}}
}
堆的调整
堆有向上调整和向下调整两种调整方式在创建时我们采用向下调整方式这样的时间复杂度比较低。故下面主要讲解向下过程(以大堆为例) 步骤如下
向下调整 1. 让parent标记需要调整的节点child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子)。 2. 如果parent的左孩子存在即:child size 进行以下操作直到parent的左孩子不存在。 1parent右孩子是否存在存在找到左右孩子中最小的孩子让child进行标记。 2将parent与较小的孩子child比较如果 aparent小于较小的孩子child调整结束。 b否则交换parent与较小的孩子child交换完成之后parent中大的元素向下移动可能导致子 树不满足对的性质因此需要继续向下调整即parent childchild parent*21; 然后继续。 以数组{ 27,15,19,18,28,34,65,49,25,37 }为例调整完变成。 对应的代码如下
如果想要转换成小堆的话把大于号小于号改一改即可故下面不在过多描述。
private void siftDown1(int parent,int end){int child parent*21;while(child end){if(child1 usedSize elem[child] elem[child1]){child;}if(elem[child] elem[parent]){swap(child,parent);parent child;child parent*21;}else{break;}}} 为了使代码整洁故再实现一个swap方法。
private void swap(int i,int j){int tmp elem[i];elem[i] elem[j];elem[j] tmp;}
注意在调整以parent为根的二叉树时必须要满足parent的左子树和右子树已经是堆了才可以向下调整。 时间复杂度分析最坏的情况即图示的情况从根一路比较到叶子比较的次数为完全二叉树的高度即时间复杂度为Olognlog下标是以2为底的。
向上调整
具体过程如图按照插入的80走的路径 代码如下
先找新结点的parent的下标再child大于0的情况下循环进行比较交换一旦发现不满足条件的立刻跳出循环因为在使用向上调整之前堆已经排序好了。
public void siftUp(int child){int parent (child-1)/2;while(child 0){if(elem[child] elem[parent]){swap(child,parent);child parent;parent (child-1)/2;}else{break;}}} 堆的创建
如图所示是从最后一个结点的父亲结点开始遍历每一个结点都调用siftdown1进行向下调整之后不断减减直到小于0下标。 代码如下 public void createBigHeap(){for(int parent (usedSize-1-1)/2;parent 0;parent--){siftDown1(parent,usedSize);}}
运行结果
通过观察elem的元素我们可以发现向下调整成功。 建堆的时间复杂度 向下调整
因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是 近似值多几个节点不影响最终结果)如图 向上调整
如图 经过比较我们选择时间复杂度较低的来进行堆的创建即向下调整至于向上调整我们用于堆的堆的插入与删除。
堆的插入与删除 堆的插入
堆的插入总共需要两个步骤 1先将元素放入到底层空间中(注意空间不够时需要扩容). 2将最后新插入的节点向上调整直到满足堆的性质. 代码如下
isFull用来判断是否需要扩容
public boolean isFull(){return usedSize elem.length;}
siftUp用来向上调整先找到新参数的parent结点 传入siftup的参数为新offer进来的参数。 public void offer(int val){//1.判断满if(isFull()){this.elem Arrays.copyOf(elem,elem.length*2);}elem[usedSize] val;usedSize;siftUp(usedSize-1);}
运行结果如下
我们可以发现成功增加数据并完成排序。 堆的删除
注意堆的删除一定删除的是堆顶元素。具体如下 1 将堆顶元素对堆中最后一个元素交换。 2 将堆中有效数据个数减少一个。 3对堆顶元素进行向下调整 。 代码如下
其实就是把最后一个元素的空间腾出来。
public int poll(){int tmp elem[0];swap(0,usedSize-1);usedSize--;siftDown1(0,usedSize);return tmp;}
运行结果如下
可以看到65被成功删除并且数组的序列没有改变 堆的应用
1.PriorityQueue的实现
可以使用堆来实现优先队列由于java语言有自带的优先队列故这里不在实现给出它的常用方法直接调用即可。
函数名功能介绍boolean offer(E e)插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常注意空间不够时候会进行扩容E peek()获取优先级最高的元素如果优先级队列为空返回nullE poll()移除优先级最高的元素并返回如果优先级队列为空返回nullint size()获取有效元素的个数void clear()清空boolean isEmpty()检测优先级队列是否为空空返回true
2.堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤
1. 建堆
升序建大堆
降序建小堆
2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。
具体过程如下
代码后序会将8大排序整理成一篇排序专项。 3.Top-k问题
TOP-K问题即求数据集合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。
比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都 不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下 1. 用数据集合中前K个元素来建堆 1前k个最大的元素则建小堆. 2前k个最小的元素则建大堆。 2. 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
不要用Arrays.sort来做这道题因为这是一道面试题用sort就可以快速结束面试回家等通知了。
top-k问题
使用堆的AC优化代码
class Imp implements ComparatorInteger{Overridepublic int compare(Integer o1,Integer o2){return o2.compareTo(o1);}}
class Solution {public int[] smallestK(int[] arr, int k) {Imp imp new Imp();PriorityQueueInteger priorityqueue new PriorityQueue(imp);int[] ans new int[k];if(k 0){return ans;}for(int i 0;i k; i){priorityqueue.offer(arr[i]);}for(int i k;i arr.length; i){int tmp priorityqueue.peek();if(arr[i] tmp){priorityqueue.poll();priorityqueue.offer(arr[i]);}}for(int i 0;i k; i){ans[i] priorityqueue.poll();}return ans;}
}
结语
其实写博客不仅仅是为了教大家同时这也有利于我巩固自己的知识点和一个学习的总结由于作者水平有限对文章有任何问题的还请指出接受大家的批评让我改进如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注这可以激励我写出更加优秀的文章。
