如何用wordpress查看搭建的站点,北京网站建设营销,做混剪素材下载网站,深圳网站建设公司怎么样1 概念解释
堆的定义#xff1a;堆是一颗完全二叉树#xff0c;分为大堆和小堆 大堆#xff1a;一棵树中#xff0c;任何父亲节点都大于等于孩子的节点#xff0c;大堆的根结点最大 小堆#xff1a;一棵树中#xff0c;任何父亲节点都小于等于孩子节点#xff0c;小堆…
1 概念解释
堆的定义堆是一颗完全二叉树分为大堆和小堆 大堆一棵树中任何父亲节点都大于等于孩子的节点大堆的根结点最大 小堆一棵树中任何父亲节点都小于等于孩子节点小堆的根节点最小
TOP K问题(元素个数远远大于K) 要求从N个数中找出前K个最大的数(N K) 方法一 假设是从100个数中找前10个最大的数先用快速排序法对数据进行降序前十个就是最大的时间复杂度O(NlogN)
方法二 将N个数依次push到大堆中那么堆顶的元素肯定是最大的然后pop K次就找到了前K个最大的数时间复杂度O(Nk*log2N后面会再次证明)。
那这是Topk问题吗 不完全是 Topk问题的前提是 N非常大若N为10亿、20亿内存中无法存下这些数只能存储在磁盘中那上面的两种方式就不适用了 思路打开可以先将前K个数建为小堆。 首先将前K个数建立成小堆 然后将剩下N-K个数不断和堆顶比较将大于堆顶的元素放入堆中后然后向下调整后最后堆中的K个数就是前K个最大的数。 时间复杂度为KN-K* logK 也就是ONlogK 注意这里建立的是小堆而不是大堆。 因为如果是大堆那么堆顶的数是堆中最大的和剩下的N-K个数比较时如果当前堆顶的数就是N个数中最大的那么就把后面的数都挡在堆外了。这种只能找到N个数中最大的数。 总结 TopK问题通过建小堆找到N个数中最大的前K个建大堆找到N个数中最小的前K个 堆排序排升序建大堆排降序建小堆 2 代码实现
建立堆的规则 若下标从1开始时其节点的计算为如下树中第一个非叶子节点直接为len(最后一个节点的索引)/2
若下标从0开始时计算父节点为**当前索引 - 1 / 2**左孩子当前索引 × 2 1右孩子2: 当前索引 ×2 2
定义
int parent(int root){return root / 2;
}
int left(int root){return root * 2;
}
int right(int root){return root * 2 1;
}上浮 //上浮public void swim(int low, int high){ //将[low...high]上浮为大顶堆从high开始由下往上int i high, j i / 2;while (j low){if (a[i] a[j]){int temp a[j];a[j] a[i];a[i] temp;i j;j i /2;}else {break;}}}下沉 //下沉public void sink(int low, int high){ //将[low...high]下沉为大顶堆从low开始由上往下int i low, j 2 * low;while (j high){if (j 1 high a[j] a[j1]){j;}if (a[j] a[i]){int temp a[i];a[i] a[j];a[j] temp;i j;j 2 * i;}else {break;}}}插入 public void insert(int num){ //插入操作插到堆的尾部然后进行上浮size;a[size] num;swim(1,size);}下沉: public int delMax(){ //去除堆顶元素删除堆的顶部元素然后进行下沉int temp a[1];a[1] a[size];size--;sink(1,size);return temp;}建堆第一种是调用插入函数从空开始建堆是向上调整。第二种是提供现成的元素数组从最后一个非叶子节点向下调整 static void TreeeAdjust(int a[], int low, int high){ //本质还是下沉操作对low所指元素下沉int i low, j 2 * low 1; //i表示父节点j表示左孩子下标从0开始 while(j high){if (j 1 high a[j] a[j1]){ //j指向左右孩子较大的那个j;}//开始下沉if(a[i] a[j]){ //什么时候下沉大顶堆-》当父节点小于子节点时小顶堆-》当父节点大于子节点时下沉int temp a[i];a[i] a[j];a[j] temp;i j;j 2 * i 1;}else {break;}}}public static void bulidBigTree (int[] arr){ //构造大顶堆int len arr.length-1;for (int i len/2 - 1; i 0; i--){TreeeAdjust(arr, i, len);}}public static void sortBigTree(int[] arr){ //堆排序交换元素以维持堆的定义。int len arr.length;int i len - 1;while (i 0){int temp arr[i];arr[i] arr[0];arr[0] temp;i--;TreeeAdjust(arr, 0,i);}}堆排序问题 升序建大顶堆然后交换堆顶和堆尾元素重复调用下沉操作 降序建大顶堆然后交换堆顶和队尾元素重复调用下沉操作两次下沉结构一样判断条件不同 大堆
static void TreeeAdjust(int a[], int low, int high){ //本质还是下沉操作int i low, j 2 * low 1; //i表示父节点j表示左孩子下标从0开始while(j high){if (j 1 high a[j] a[j1]){j;}if(a[i] a[j]){ //什么时候下沉大顶堆-》当父节点小于子节点时小顶堆-》当父节点大于子节点时下沉int temp a[i];a[i] a[j];a[j] temp;i j;j 2 * i 1;}else {break;}}}public static void bulidBigTree (int[] arr){ //构造大顶堆int len arr.length-1;for (int i len/2 - 1; i 0; i--){TreeeAdjust(arr, i, len);}}public static void sortBigTree(int[] arr){ //堆排序交换元素以维持堆的定义。int len arr.length;int i len - 1;while (i 0){int temp arr[i];arr[i] arr[0];arr[0] temp;i--;TreeeAdjust(arr, 0,i);}}建立大堆和小堆关键的区别就在于下沉操作的判断条件 将圈中的判断改成就变成小堆 大堆下沉 当父节点小于子节点时和较大的子节点交换位置 小堆下沉当父节点大于子节点时和较小的子节点交换位置 大堆上升子节点大于父节点直接判断 小堆上升当子节点小于父节点直接判断 每次分析时按照这个最小的单位进行分析上浮和下沉
3优先级队列
Java 优先队列 PriorityQueue
Java 优先队列默认是小顶堆小的先出队。
PriorityQueueInteger pq new PriorityQueue()建立大顶堆
PriorityQueueInteger pq new PriorityQueue((a, b)-(b-a));2.其他排序规则 //将pair按照key从大到小排序key相同情况下按照value从小到大排序。PriorityQueuePairInteger, Integer pq new PriorityQueue(n, new ComparatorPairInteger, Integer() {public int compare(PairInteger, Integer o1, PairInteger, Integer o2) {if(o1.getKey() - o2.getKey() 0) {return 1;} else if(o1.getKey() - o2.getKey() 0){if(o1.getValue() - o2.getValue() 0) {return -1;} else {return 1;}}return -1;}});
// 在数组情况下pair的key为数组值value为下标
// 实现上述排序的一种巧妙做法。注nums[] 为数组
PriorityQueueInteger pqMin new PriorityQueue(new ComparatorInteger() {public int compare(Integer o1, Integer o2) {if(nums[o1] - nums[o2] 0) {return -1;} else if(nums[o1] - nums[o2] 0){if(o1 - o2 0) {return -1;}}return 1;}});PriorityQueueInteger pqMax new PriorityQueue(new ComparatorInteger() {public int compare(Integer o1, Integer o2) {if(nums[o1] - nums[o2] 0) {return -1;} else if(nums[o1] - nums[o2] 0){if(o1 - o2 0) {return -1;}}return 1;}});//Lambda表达式PriorityQueueInteger pq new PriorityQueue((a, b)-(b-a));
优先队列常用方法
public boolean add(E e); //在队尾插入元素插入失败时抛出异常并调整堆结构
public boolean offer(E e); //在队尾插入元素插入失败时抛出false并调整堆结构public E remove(); //获取队头元素并删除并返回失败时前者抛出异常再调整堆结构
public E poll(); //获取队头元素并删除并返回失败时前者抛出null再调整堆结构public E element(); //返回队头元素不删除失败时前者抛出异常
public E peek()//返回队头元素不删除失败时前者抛出nullpublic boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素从队头到队尾遍历
public IteratorE iterator(); //迭代器
插入元素 offer方法返回值boolean再次调整堆结构
删除元素 poll方法返回堆顶元素再次调整堆结构
获取堆头元素 peek方法返回堆顶元素
判断队列是否为空** isEmpty(); **
获取队列中元素个数**size(); **
判断队列中是否包含指定元素从队头到队尾遍历**contains(Object o); ** 参考链接 https://blog.csdn.net/weixin_46016019/article/details/123774875
