(转)算法之优先队列 PriorityQueue解决Top K 问题

转自:https://www.jianshu.com/p/a4a1984fc4ff

解决方法:
维护一个大小为 K 的小顶堆,依次将数据放入堆中,当堆的大小满了的时候,只需要将堆顶元素与下一个数比较:如果大于堆顶元素,则将当前的堆顶元素抛弃,并将该元素插入堆中。遍历完全部数据,Top K 的元素也自然都在堆里面了。

当然,如果是求前 K 个最小的数,只需要改为大顶堆即可

将数据插入堆 95 大于 20,进行替换 95 下沉,维持小顶堆
对于海量数据,我们不需要一次性将全部数据取出来,可以一次只取一部分,因为我们只需要将数据一个个拿来与堆顶比较。

另外还有一个优势就是对于动态数组,我们可以一直都维护一个 K 大小的小顶堆,当有数据被添加到集合中时,我们就直接拿它与堆顶的元素对比。这样,无论任何时候需要查询当前的前 K 大数据,我们都可以里立刻返回给他。

整个操作中,遍历数组需要 O(n) 的时间复杂度,一次堆化操作需要 O(logK),加起来就是 O(nlogK) 的复杂度,换个角度来看,如果 K 远小于 n 的话, O(nlogK) 其实就接近于 O(n) 了,甚至会更快,因此也是十分高效的。

最后,对于 Java,我们可以直接使用优先队列 PriorityQueue 来实现一个小顶堆,这里给个代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static List<Integer> solutionByHeap(int[] input, int k) {
List<Integer> list = new ArrayList<>();
if (k > input.length || k == 0) {
return list;
}
Queue<Integer> queue = new PriorityQueue<>();
for (int num : input) {
if (queue.size() < k) {
queue.add(num);
} else if (queue.peek() < num) {
queue.poll();
queue.add(num);
}
}
while (k-- > 0) {
list.add(queue.poll());
}
return list;
}

关于位运算和HashMap中一个求最小2次幂的算法

今天在HashMap的内部源码的时候,看到这样一个算法:

/**
 * Returns a power of two size for the given target capacity.
 * 返回大于或等于 cap 的最小2次幂
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

第一眼看起来确实是一脸懵逼,通过只知道这是一个获取该数的大于或等于 cap 的最小2次幂,这么厉害,咋实现的呀?

1、数据在内存中如何存储?

我们知道”<<” 和 “>>” 分别代表 左移和右移位运算符号,表示 乘以2 和除以2(大多数时候适用),”>>>”还是第一次见,这是代表什么意思呢?说到这里我们不得不去了解一下数据是如何存储在内存中的:

在32位的计算机系统中,int型数据占几个字节? 4字节。其中每个字节有8个比特位,表示二进制位,位是计算机内部数据储存的最小单位。这是所有编程语言学习者都知道的。也就是说 int类型在内存中有4*8 == 32个比特为 所以如果以整形数10为例,那么它在内存中完整存储的形式为:

00000000 00000000 00000000 00001010 ->对应 1x2^3+0x2^2+1x2^1+0x2^0 =10

那么int类型表示最大的数是不是就是:

11111111 11111111 11111111 11111111 ->对应 1x2^31+1x2^30…1x2^1+1x2^0

但为我们知道int类型的最大值为:2^31-1,显然上面的答案不是正确的。

这是因为在所有被int类型占用的比特位中,左起第一个位(即最高位)就是符号位。int类型的符号位上,0表示正数,1表示负数。在32位操作系统下,其余后面31位是数值位。也就是说:

11111111 11111111 11111111 11111111 所代表的数字为:1x2^30+1x2^29…1x2^1+1x2^0 的相反数为:-(2^31-1)

这里需要注意的是,按原先的逻辑去理解的话

00000000 00000000 00000000 00000000 为+0

10000000 00000000 00000000 00000000 为-0

那他们表示的意义是一样的么?
实际上,在32位系统下int类型中,我们计算机已经强行规定了这种情况,数字0采用“+0”的表示方法,即 00000000 00000000 00000000 00000000;而“-0”这个特殊的数字被定义为了-2^31。

因此我们看到32位系统下int类型的取值范围中,负数部分比正数部分多了一个数字,正数的最大取值是2^31-1,而负数的最小取值是-2^31。正数部分之所以要减去1,是因为被数字0占用了“+0”,而负数部分不需要用来表示0,因此原本的“-0”就用来表示-2^31这个数字。

2、位运算如何进行?

至此我们明白了数据在计算机中的存储形式,那位运算具体怎么运行的呢?
以10和-10为例,其二进制完整表示为:00000000 00000000 00000000 00001010 和 10000000 00000000 00000000 00001010 为了便于观察,我们取后面8位:00001010

  • 对于符号位移

例如将10的二进制向左移1位:那么变成 0001010 0 == 20 原先二进制数的第一位被移除,而最后一位被舍弃。将10的二进制向右移1位 原先二进制数最后一位被移除,第一位补0,则变成 000101 ==5

如将-10的二进制向左移1位, 10000000 00000000 00000000 00001010则变成:

10000000 00000000 00000000 0010100 为-20

如将-10的二进制向右移1位, 10000000 00000000 00000000 00001010则变成 :

注意这里多了一个0-> 1 00000000 00000000 00000000 0000101 <-注意这里少了位

也就是说符号移动,会保留原来的符号位,不会因为右移左移而带走符号位。

  • 对于无符号位移

相反无符号位移会不关注符号位。
例如将-10向右无符号右移就会变成:

010000000 00000000 00000000 0000101 变成了一个很大的正数了!!

如果将-10无符号左移,则变成:

00000000 00000000 00000000 00001010 = 20

但是!!并没有无符号左移动这样一件事情!
跟右移运算不同的是,无符号左移和左移是一样的。因此java没有无符号左移运算。(<<<和<<<=将报错)

因为无符号右移运算需要考虑符号位的右移,而符号位只存在于二进制表示的最左边,最右边没有。所以不用区分无符号左移和左移运算。

3、关于返回大于或等于 cap 的最小2次幂的算法

我们以传入10为例子

由这张图看起来,算法很容易懂了,其实最主要的是为了去让各个位从高到低 从0变成1或者维持1不变,这样就能找到该数最小的2次幂

另外,需要注意一下的是,第一步 int n = cap - 1; 这个操作,执行这个操作的主要原因是为了防止在cap已经是2的n次幂的情况下,经过运算后得到的结果是cap的二倍的结果,例如如果n为l6,经过一系列运算之后,得到的结果是0001 1111,此时最后一步n+1 执行之后,就会返回32,有兴趣的可以自己进行尝试;

小弟不才,如有问题,欢迎指出。

参考来源:

https://blog.csdn.net/c10WTiybQ1Ye3/article/details/89411471
https://www.jianshu.com/p/927009730809

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×