南昌seo网站建设,桂林创新大厦网站,长沙电子商务公司网站制作,三合一网站cmsJava实现最小堆一堆是一种经过排序的完全二叉树#xff0c;其中任一非终端节点的数据值均不大于(或不小于)其左孩子和右孩子节点的值。最大堆和最小堆是二叉堆的两种形式。最大堆#xff1a;根结点的键值是所有堆结点键值中最大者。最小堆#xff1a;根结点的键值是所有堆结…Java实现最小堆一堆是一种经过排序的完全二叉树其中任一非终端节点的数据值均不大于(或不小于)其左孩子和右孩子节点的值。最大堆和最小堆是二叉堆的两种形式。最大堆根结点的键值是所有堆结点键值中最大者。最小堆根结点的键值是所有堆结点键值中最小者。就像下面这棵树一样。这棵二叉树有一个特点就是所有父结点都比子结点要小(注意圆圈里面的数是值圆圈上面的数是这个结点的编号此规定仅适用于本节)。符合这样特点的完全二叉树我们称为最小堆。反之如果所有父结点都比子结点要大这样的完全二叉树称为最大堆。那这一特性究竟有什么用呢 假如有14个数分别是99、5、36、7、22、17、46、12、2、19、25、28、1和92。请找出这14个数中最小的数请问怎么办呢最简单的方法就是将这14个数从头到尾依次扫一遍用一个循环就可以解决。这种方法的时间复杂度是O(14)也就是O(N)。for(i1;i14;i){if(a[i]{mina[i];}}现在我们需要删除其中最小的数并增加一个新数23再次求这14个数中最小的一个数。请问该怎么办呢只能重新扫描所有的数才能找到新的最小的数这个时间复杂度也是O(N)。假如现在有14次这样的操作(删除最小的数后并添加一个新数)。那么整个时间复杂度就是O(142)即O(N2)。那有没有更好的方法呢堆这个特殊的结构恰好能够很好地解决这个问题。首先我们先把这个14个数按照最小堆的要求(就是所有父结点都比子结点要小)放入一棵完全二叉树就像下面这棵树一样。很显然最小的数就在堆顶假设存储这个堆的数组叫做h的话最小数就是h[1]。接下来我们将堆顶的数删除并将新增加的数23放到堆顶。显然加了新数后已经不符合最小堆的特性我们需要将新增加的数调整到合适的位置。那如何调整呢向下调整我们需要将这个数与它的两个儿子2和5比较并选择较小一个与它交换交换之后如下我们发现此时还是不符合最小堆的特性因此还需要继续向下调整。于是继续将23与它的两个儿子12和7比较并选择较小一个交换交换之后如下到此还是不符合最小堆的特性仍需要继续向下调整直到符合最小堆的特性为止。我们发现现在已经符合最小堆的特性了。综上所述当新增加一个数被放置到堆顶时如果此时不符合最小堆的特性则将需要将这个数向下调整直到找到合适的位置为止使其重新符合最小堆的特性。我们刚才在对23进行调整的时候竟然只进行了3次比较就重新恢复了最小堆的特性。现在最小的数依然在堆顶为2。之前那种从头到尾扫描的方法需要14次比较现在只需要3次就够了。现在每次删除最小的数并新增一个数并求当前最小数的时间复杂度是O(3)假如现在有1亿个数(即N1亿)进行1亿次删除最小数并新增一个数的操作使用原来扫描的方法计算机需要运行大约1亿的平方次而现在只需要1亿*log1亿次即27亿次。假设计算机每秒钟可以运行10亿次那原来则需要一千万秒大约115天而现在只要2.7秒。是不是很神奇再次感受到算法的伟大了吧。说到这里如果只是想新增一个值而不是删除最小值又该如何操作呢即如何在原有的堆上直接插入一个新元素呢只需要直接将新元素插入到末尾再根据情况判断新元素是否需要上移直到满足堆的特性为止。如果堆的大小为N(即有N个元素)那么插入一个新元素所需要的时间也是O(logN)。例如我们现在要新增一个数3。先将3与它的父结点25比较发现比父结点小为了维护最小堆的特性需要与父结点的值进行交换。交换之后发现还是要比它此时的父结点5小因此需要再次与父结点交换。至此又重新满足了最小堆的特性。向上调整完毕后如下。END
