--- title: 堆 vs 胜者树 vs 败者树 categories: [算法&数据结构] --- ## 外部排序算法 **本文介绍这三种数据结构是因为在外部排序算法中进行多路归并时，常常需要在内存中选择多路数据中的最小值，而这三者都能实现相同的功能，因此放在一起比较。** **对外部排序算法熟悉的读者可以跳过该小节。** ![image-20241119140000955](https://cdn.jsdelivr.net/gh/NOS-AE/assets@main/img/image-20241119140000955.png) 外部排序是用于对超出计算机内存容量的大型数据集进行排序的一种算法。在排序过程中，需要将数据集分成多个较小的子集，并在内存中对每个子集进行排序，然后再将排序后的子集合并起来。这种算法通常会利用硬盘等外部存储设备来协助处理数据，因此被称为“外部排序”。 外部排序的好处和必要性在于： - 内存无法装入大量待排序数据，使用外部排序算法可以避免占用过多的内存。 - 外部排序算法还可以通过将数据集分成多个块并对每个块进行并行处理来进一步提高性能。 多路归并算法通常使用一个优先队列（也称为最小堆）来保存各个子集中的数据。在合并过程中，首先从各个子集中读取一个元素，并将它们插入到优先队列中。队列会自动将它们排序，因此队列顶端的元素是当前最小的元素。我们将队列顶端的元素取出，并将它插入到磁盘文件中。然后我们从该元素所在的子集中读取下一个元素，并将它插入到队列中，这样队列中的元素数保持不变。这个过程一直重复，直到所有元素都被读取出来，合并完成。 ## 堆 **堆（Heap）是一种特殊的完全二叉树**数据结构，分为**最大堆**和**最小堆**： - **最大堆**：每个节点的值都大于等于其子节点，根节点是最大值。 - **最小堆**：每个节点的值都小于等于其子节点，根节点是最小值。 堆常用于实现**优先队列**，支持快速获取最大值或最小值，基本操作（插入和删除）时间复杂度为 O(logn)。 具体操作如下： 1. 取出一个元素总是发生在堆顶，因为堆顶的元素是最小的（小顶堆中）。 2. 使用堆中最后一个元素来填补空缺位置 3. 对顶部元素进行下沉，如果左右孩子有比自己小的，则选择选择最小的那个进行交换。重复进行下沉操作，以满足堆的性质。**即每次下沉需要进行两次比较操作** ## 胜者树 **胜者树（Winner Tree）是一种特殊的完全二叉树**，用于多路归并排序。它的叶子节点表示参与归并的多个数据流，非叶子节点存储比较中获胜者（较小或较大值），根节点最终存储全局最小值或最大值。 胜者树支持快速找到当前最小值并动态更新（时间复杂度 O(logk)，k 为数据流数量），常用于**归并排序**和**流式处理**场景。 胜者树满足： - 胜者树一棵完全二叉树。其中的叶结点是要排序的元素，非叶结点是两个子结点中胜者的代表。 - 根节点代表着所有元素中的胜者。 ![img](https://cdn.jsdelivr.net/gh/NOS-AE/assets@main/img/82f4a151bd608aafa76c7a651972bd50.png) **当每次有新的元素填充进来，需要不断上浮，每次上浮与兄弟元素比较一次即可，但是每个节点指向的是父节点，而不是兄弟节点，所以需要先拿到父节点才能拿到兄弟节点，即上浮需要两次访存** ## 败者树 败者树是胜者树的一种变体，它也是一棵完全二叉树。和胜者树不同的是，败者树的节点存储的是败者：在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。 ![img](https://cdn.jsdelivr.net/gh/NOS-AE/assets@main/img/50c0040da3117dc352dc242331c0120b.png) **当每次有新的元素填充进来，需要不断上浮，每次上浮与父节点比较一次即可，即一次访存** ## 总结 - 堆：每次新增元素需要下沉元素，每次下沉需要两次访存+两次比较 - 胜者树：每次新增元素需要上浮元素，每次上浮需要两次访存+一次比较 - 败者树：每次新增元素需要上浮元素，每次上浮需要一次访存+一次比较 ## 参考