赣州市做网站设计,为什么选php语言做网站,微表单网站,旅游网页图片一、基础知识
1.1 什么是最大#xff08;小#xff09;堆
最大堆#xff0c;最小堆类似#xff0c;以下以最小堆为例进行讲解。 最小堆是满足以下条件的数据结构#xff1a;
它是一棵完全二叉树所有父节点的值小于或等于两个子节点的值
1.2 什么是完全二叉树
除了最后…一、基础知识
1.1 什么是最大小堆
最大堆最小堆类似以下以最小堆为例进行讲解。 最小堆是满足以下条件的数据结构
它是一棵完全二叉树所有父节点的值小于或等于两个子节点的值
1.2 什么是完全二叉树
除了最后一层之外的其他每一层都被完全填充并且所有结点都保持向左对齐。
1.3 什么是TOP K问题
Top K指的是从n很大个数据中选取最大小的k个数据。例如学校要从全校学生中找到成绩最高的500名学生再例如某搜索引擎要统计每天的100条搜索次数最多的关键词。
二、堆排序解决TOP K
对于TOPK问题解决方法有很多
方法一对源数据中所有数据进行排序取出前K个数据就是TopK。
但是当数据量很大时只需要k个最大的数整体排序很耗时效率不高。
方法二维护一个K长度的数组a[]先读取源数据中的前K个放入数组对该数组进行升序排序再依次读取源数据第K个以后的数据和数组中最小的元素a[0]比较如果小于a[0]直接pass大于的话就丢弃最小的元素a[0]利用二分法找到其位置然后该位置前的数组元素整体向前移位直到源数据读取结束。
这比方法一效率会有很大的提高但是当K的值较大的时候长度为K的数据整体移位也是非常耗时的。
对于这种问题效率比较高的解决方法是使用最小堆。
2.1 最小堆思路
最小堆小根堆是一种数据结构它首先是一棵完全二叉树并且它所有父节点的值小于或等于两个子节点的值。
最小堆的存储结构物理结构实际上是一个数组。如下图 堆有几个重要操作
BuildHeap将普通数组转换成堆转换完成后数组就符合堆的特性所有父节点的值小于或等于两个子节点的值。
Heapify(int i)当元素i的左右子树都是小根堆时通过Heapify让i元素下降到适当的位置以符合堆的性质。
回到上面的取TopK问题上用最小堆的解决方法就是先去源数据中的K个元素放到一个长度为K的数组中去再把数组转换成最小堆。再依次取源数据中的K个之后的数据和堆的根节点数组的第一个元素比较根据最小堆的性质根节点一定是堆中最小的元素如果小于它则直接pass大于的话就替换掉跟元素并对根元素进行Heapify直到源数据遍历结束。
2.2 最小堆解决TOPK
最小堆的实现
public class MinHeap
{// 堆的存储结构 - 数组private int[] data;// 将一个数组传入构造方法并转换成一个小根堆public MinHeap(int[] data){this.data data;buildHeap();}// 将数组转换成最小堆private void buildHeap(){// 完全二叉树只有数组下标小于或等于 (data.length) / 2 - 1 的元素有孩子结点遍历这些结点。// *比如上面的图中数组有10个元素 (data.length) / 2 - 1的值为4a[4]有孩子结点但a[5]没有*for (int i (data.length) / 2 - 1; i 0; i--) {// 对有孩子结点的元素heapifyheapify(i);}}private void heapify(int i){// 获取左右结点的数组下标int l left(i); int r right(i);// 这是一个临时变量表示 跟结点、左结点、右结点中最小的值的结点的下标int smallest i;// 存在左结点且左结点的值小于根结点的值if (l data.length data[l] data[i]) smallest l; // 存在右结点且右结点的值小于以上比较的较小值if (r data.length data[r] data[smallest]) smallest r; // 左右结点的值都大于根节点直接return不做任何操作if (i smallest) return; // 交换根节点和左右结点中最小的那个值把根节点的值替换下去swap(i, smallest);// 由于替换后左右子树会被影响所以要对受影响的子树再进行heapifyheapify(smallest);}// 获取右结点的数组下标private int right(int i){ return (i 1) 1; } // 获取左结点的数组下标private int left(int i) { return ((i 1) 1) - 1; }// 交换元素位置private void swap(int i, int j) { int tmp data[i]; data[i] data[j]; data[j] tmp; }// 获取对中的最小的元素根元素public int getRoot(){return data[0];}// 替换根元素并重新heapifypublic void setRoot(int root){data[0] root;heapify(0);}
}利用最小堆获取TopK
public class TopK
{public static void main(String[] args){// 源数据int[] data {56,275,12,6,45,478,41,1236,456,12,546,45};// 获取Top5int[] top5 topK(data, 5);for(int i0;i5;i){System.out.println(top5[i]);}}// 从data数组中获取最大的k个数private static int[] topK(int[] data,int k){// 先取K个元素放入一个数组topk中int[] topk new int[k]; for(int i 0;i k;i){topk[i] data[i];}// 转换成最小堆MinHeap heap new MinHeap(topk);// 从k开始遍历datafor(int i k;idata.length;i){int root heap.getRoot();// 当数据大于堆中最小的数根节点时替换堆中的根节点再转换成堆if(data[i] root){heap.setRoot(data[i]);}}return topk;
}
}2.3 最小堆的删除操作
前面在介绍最小堆解决TOPK问题的时候已经涉及到建堆、添加元素的过程接下来介绍最小堆的删除过程。
操作原理是当删除节点的数值时原来的位置就会出现一个孔,填充这个孔的方法就是 把最后的叶子的值赋给该孔并下调到合适位置最后把该叶子删除。
如图中要删除72,先用堆中最后一个元素来35替换72,再将35下沉到合适位置,最后将叶子节点删除。 “结点下沉”
