计算机思维：二叉树的应用（树形选择排序)【面试题】

引言

善于掌握工具（锦标赛排序），可以弥补智力上的不足，工具的发明是针对问题来的。

1. 在数学上要计算数字，人类就发明了算盘。
2. 在物理学上，要测量绝对的数值，人类就发明了各种度量长度的尺子、计时的钟、称重量的天平和秤等等。
3. 在化学上，要测量化学反应的当量，人类就发明了各种有刻度的量器。
4. 在计算机科学中，数据的相对大小比绝对的数值重要，出于很多数据比大小的需求以及其他一些需求，就产生了一个抽象的数据结构——二叉树。https://blog.csdn.net/z929118967/article/details/123693521?spm=1001.2014.3001.5501

在计算机中，由于经常要做的事情是判断真假、比较大小、排序、挑选最大值这类的操作，而它们在计算机的世界里又如此重要，当然也就值得为这些事情专门设计一种数据结构，这种数据结构被称为二叉树。

I 树形选择排序

树形选择排序也称为“锦标赛排序法”。

1.1 锦标赛排序算法

单淘汰的锦标赛中，选手们两两比赛，胜者晋级，败者被淘汰, 把比赛的赛程和结果对应成一个二叉树。

在树中每一个选手是二叉树中的一个叶子结点，每一场比赛就相当于两个数字在比大小。数字大的选手获胜进入下一轮，也就是说比大小，大的那个选手，进入上一层，成为枝干上的根。所以，进入到某一轮比赛的选手，其实都是某个子树干的根结点。最后的冠军是整个二叉树的根结点。

赛制的合理性来自一个假设：“输赢的传递性”，如果张三赢了李四，李四赢了王五，那么张三一定能赢王五。

A>B, B>C, 那么必然有A>C。

1.2 排序步骤

1. 把所有的数字放到二叉树的叶子结点，然后按照锦标赛单淘汰的方式，两两比较选出最大的。
2. 从所有被最大的数字淘汰的数字（叶子节点）中选择第二大（执行第一步）。
3. 对于第三、第四大的数字，可以以此类推（重新选择叶子结点数组）。

1.3 算法的复杂度

算法的复杂度:是N乘以Log N，和快速排序差不多。这种方法在从N个选手中选出K个选手的事情中特别快。

比如说，如果我们只需要选出第一名，这种算法的复杂度只有N，不是N乘以Log N。如果还需要选出第二名，则额外增加Log N次计算就可以了，对第三名也是如此。

II 树形选择排序的应用：从25个选手中赛出前三名

2.1 问题

有二十五名短跑选手比赛竞争金银铜牌，赛场上有五条赛道，因此一次可以有五个人同时比赛。比赛并不计时，只看相应的名次。假如选手的发挥是稳定的，最少需要几组比赛才能决出前三名。

答案：7次

2.2 比赛方案（善用信息）

第一步：将25名选手分为五个组，每组五个人，不妨把这25人根据所在的组进行编号，A1-A5在A组，B1-B5在B组……最后E1-E5在最后的E组。然后让每个组分别比赛，排出各组的名次来。不失一般性，假设他们的名次就是他们在小组中的编号，即A组的名次是A1、A2、A3、A4、A5，B组和其它组的名次也是类似（如下图）：

第二步：让各组的第一名，也就是A1、B1、C1、D1、E1再比一次，上图中是第一排红颜色的，这样就能决出第一名。不失一般性，我们假设A1在这次比赛中获胜，这样我们就知道了第一名。

第三步：第二、三名的候选人一共只有五个，即A2、A3、B1、B2和C1，刚好凑一组，让他们五个人再跑一次即可。

在第六组比赛（五个第一名的比赛）结束之后，最后的两名已经没有资格决逐前三名了。

• 第二名的候选：输给第一名的A2、B1
• 第三名的候选：输给第二名候选人的A3、B2、C1

和A1在某一组比赛的第三名A3、C1 输给第二名候选人B1的B2。

III Google面试题：设计一个车载地图功能，找到最近的加油站。

3.1 设计

1. 搞清楚每一个加油站的位置和汽车现在的位置，搞清楚行车方向。
2. 距离的计算：找到上千种路线中最短的一条。利用数学中的动态规划，把汽车和城市里所有的加油站之间的距离列一个表。加油站G1，距离D1；加油站G2，距离D2；
3. 按照距离排序，找出最近的几个加油站。

3.2 优化

大数据思维：把所有数据集中起来，进行全局优化。

1. 考虑真实的应用场景，很多计算都是可以预先算好的，等到服务的时候，直接把结果调出来即可，而不需要做重复计算。
2. 在大数据的很多应用中，我们通常只关心前几个，而不需要对所有的数据排序。

在二叉树这种数据结构中，有一种更特殊的细类，被称为“堆”，用这种数据结构，就可以做到只排出前几名，而不用管后面的名次。

3.3 Java 堆排序

提高效率的本质：少做事情（效率＝产出／所做的事情）【 衡量算法的标准-算法复杂度】

https://blog.csdn.net/z929118967/article/details/131809460思想：基于二叉堆的排序算法，它利用了堆的性质来进行排序。

堆排序分为两个主要步骤：建堆和排序。

• 建堆的过程是将待排序的数组构建成一个二叉堆，通常使用最大堆（大顶堆）来进行排序。
• 排序的过程是不断地从堆顶取出最大值（根节点），将其与堆中最后一个元素交换，然后重新调整堆，使得剩余元素仍满足堆的性质。

//定义了一个 heapSort 方法，它接受一个整数数组作为参数，然后对数组进行堆排序。
//在排序过程中，首先通过 heapify 方法建立一个最大堆。
//然后，从数组末尾开始，将最大值（根节点）与当前位置的元素交换，接着调整堆，使得交换后的剩余元素仍满足堆的性质。
//最终，通过不断重复这个过程，得到一个有序的数组。

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 建堆（构造最大堆）
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 排序
        for (int i = n - 1; i > 0; i--) {
            // 将当前最大值（根节点）与最后一个元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 调整堆，使剩余元素仍满足最大堆性质
            heapify(arr, i, 0);
        }
    }

    public static void heapify(int[] arr, int n, int i) {
        int largest = i;  // 初始化最大值为当前节点
        int left = 2 * i + 1;  // 左子节点索引
        int right = 2 * i + 2;  // 右子节点索引

        // 如果左子节点大于最大值节点，更新最大值节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 如果右子节点大于最大值节点，更新最大值节点
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 如果最大值节点不是当前节点，交换节点并递归调整堆
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 2, 4};
        heapSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

see also

计算机思维之【计算机数据结构的出现与计算机本身的关系】https://kunnan.blog.csdn.net/article/details/115913603