【Data Structure】优先队列（Priority Queue）

Background

队列（Queue）

队列的特点是什么？

聪明的小伙伴们都知道，是先进先出（FIFO）。

Posted by Wei on 2019-07-31, Last Modified on 2025-03-25

【Algorithm】排序算法 - 桶排序（Bucket Sort）

Idea

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

思路

设置固定空桶数
将数据放到对应的空桶中
将每个不为空的桶进行排序
拼接不为空的桶中的数据，得到结果

步骤演示

假设一组数据（长度为 20）为

[63,157,189,51,101,47,141,121,157,156,194,117,98,139,67,133,181,13,28,109]

现在需要按 5 个分桶，进行桶排序，实现步骤如下:

找到数组中的最大值 194 和最小值 13，然后根据桶数为 5，计算出每个桶中的数据范围为 (194-13+1)/5=36.4；
遍历原始数据，以第一个数据 63 为例，先找到该数据对应的桶序列（Math.floor(63 - 13) / 36.4) =1），然后将该数据放入序列为 1 的桶中（从 0 开始算）；
当向同一个桶中第二次插入数据时，判断桶中已存在的数字与新插入的数字的大小，按从左到右，从小打大的顺序插入。如第一个桶已经有了 63，再插入 51，67 后，桶中的排序为 (51,63,67) ，一般通过链表来存放桶中数据。
全部数据装桶完毕后，按序列，从小到大合并所有非空的桶（0，1，2，3，4 桶）
合并完之后就是排序好的数据了

...

Posted by Wei on 2019-07-30, Last Modified on 2024-01-23

【Algorithm】TopK 问题

有 1 亿个浮点数，如果找出期中最大的 10000 个？

排序

最容易想到的方法是将数据全部排序，然后在排序后的集合中进行查找，最快的排序算法的时间复杂度一般为 O（nlogn），如快速排序。

但是在 32 位的机器上，每个 float 类型占 4 个字节，1 亿个浮点数就要占用 400MB 的存储空间，对于一些可用内存小于 400M 的计算机而言，很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求（我机器内存都是 8GB），该方法也并不高效，因为题目的目的是寻找出最大的 10000 个数即可，而排序却是将所有的元素都排序了，做了很多的无用功。

局部淘汰法

第二种方法为局部淘汰法，该方法与排序方法类似，用一个容器保存前 10000 个数，然后将剩余的所有数字 —— 与容器内的最小数字相比，如果所有后续的元素都比容器内的 10000 个数还小，那么容器内这个 10000 个数就是最大 10000 个数。

如果某一后续元素比容器内最小数字大，则删掉容器内最小元素，并将该元素插入容器，最后遍历完这 1 亿个数，得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为 $O （ n + m^{2} ）$ ，其中 m 为容器的大小，即 10000。

分治法

第三种方法是分治法，将 1 亿个数据分成 100 份，每份 100 万个数据，找到每份数据中最大的 10000 个，最后在剩下的 100*10000 个数据里面找出最大的 10000 个。

如果 100 万数据选择足够理想，那么可以过滤掉 1 亿数据里面 99% 的数据。100 万个数据里面查找最大的 10000 个数据的方法如下：用快速排序的方法，将数据分为 2 堆，如果大的那堆个数 N 大于 10000 个，继续对大堆快速排序一次分成 2 堆，如果大的那堆个数 N 大于 10000 个，继续对大堆快速排序一次分成 2 堆，如果大堆个数 N 小于 10000 个，就在小的那堆里面快速排序一次，找第 10000-n 大的数字；递归以上过程，就可以找到第 1w 大的数。参考上面的找出第 1w 大数字，就可以类似的方法找到前 10000 大数字了。此种方法需要每次的内存空间为 10^6*4=4MB，一共需要 101 次这样的比较。

...

Posted by Wei on 2019-07-30, Last Modified on 2023-10-11

【Java】I/O - 读取数据

Java Scanner 类

java.util.Scanner 是 Java5 的新特征，我们可以通过 Scanner 类来获取用户的输入。

下面是创建 Scanner 对象的基本语法：

Scanner s = new Scanner(System.in);

接下来我们演示一个最简单的数据输入，并通过 Scanner 类的 next () 与 nextLine () 方法获取输入的字符串，在读取前我们一般需要使用 hasNext 与 hasNextLine 判断是否还有输入的数据。

next 方法

public class ScannerDemo {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 从键盘接收数据
 
        // next方式接收字符串
        System.out.println("next方式接收：");
        // 判断是否还有输入
        if (scan.hasNext()) {
            String str1 = scan.next();
            System.out.println("输入的数据为：" + str1);
        }
        scan.close();
    }
}

...

Posted by Wei on 2019-07-30, Last Modified on 2025-04-23

【Algorithm】排序算法 - 堆排序（Heap Sort）

堆排序（Heap Sort）

堆排序是利用 ** 二叉堆（Binary Heap）这种数据结构而设计的一种排序算法，堆排序是一种选择排序，** 它的最坏，最好，平均时间复杂度均为 $O (n l o g_{2} n)$ ，它是一种不稳定排序。首先简单了解下堆结构。

堆是具有以下性质的完全二叉树：

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（Max Heap）；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆（Min Heap）。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆的存储

一般都用数组来表示堆，i 结点的父结点下标就为 (i – 1) // 2。它的左右子结点下标分别为 2i + 1 和 2i + 2。如第 0 个结点的左右子结点的下标分别为 1 和 2。

...