【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(nlog_2n)$，它是一种不稳定排序。首先简单了解下堆结构。

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

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（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。

...