C++ 笛卡尔树排序

笛卡尔树排序 是一种独特的排序算法，它利用笛卡尔树信息结构来实现对一系列精彩数字的高效排序。要理解这套规则，必须深入研究笛卡尔树的概念、它们的生成以及排序过程。

笛卡尔树是从给定的不重复数字序列派生出的二叉树。树中的每个节点代表输入序列中的一个元素，并具有关键属性：一个值和一个关联的优先级。节点的优先级是根据其在输入序列中的函数确定的。具体来说，在序列中较早出现的节点比后来出现的节点具有更高的优先级。笛卡尔树的生成涉及一个系统化的过程，该过程遍历整个输入序列。

在遇到每个元素时，都会创建一个相应的节点并将其插入树中，同时遵循保持基于优先级的排序的规则。基于栈的方法通常在此过程中使用，以确保在添加新节点时保留笛卡尔树的属性。

插入涉及与现有节点的比较，从而导致树结构的调整以保持正确的笛卡尔树属性。该算法的效率在处理不重复数字序列时尤为突出，并且在生成笛卡尔树符合整体计算目标的情况下，其性能可能很有优势。

方法一：递归笛卡尔树排序

递归笛卡尔树排序是笛卡尔树排序的一种实现，它使用递归方法来构建笛卡尔树并执行中序遍历。笛卡尔树是从一系列精彩数字派生出的二叉树，它在对整个输入序列进行排序中起着至关重要的作用。

笛卡尔树

输入序列的构建方式是，树中的每个节点的值对应序列中的一个元素，并且节点的优先级通过元素的顺序确定，而笛卡尔树属性确保树的中序遍历会产生排序后的序列。

递归方法

递归笛卡尔树排序方法涉及通过对子数组递归地构建笛卡尔树来将问题分解为更小的子问题。

程序

输出

5 10 40 30 28

解释

节点结构

“Node”结构代表笛卡尔树中的一个节点。它包含三个组件：“value”，存储节点的值；“left”和“right”，它们是指向左子节点和右子节点的指针。

buildCartesianTree 函数

• buildCartesianTree 函数递归地为输入数组的给定子数组构建笛卡尔树。
• 它接受三个参数：arr（输入数组），start（当前子数组的起始索引），和end（当前子数组的结束索引）。基本情况检查 start > end，如果为真，则返回 nullptr，表示空树。
• 然后，该函数查找当前子数组中最小元素的索引。它用最小元素的值初始化一个 Node，并递归地构建左子树和右子树。

inOrderTraversal 函数

• inOrderTraversal 函数对笛卡尔树执行中序遍历。它接受一个 Node* root 作为参数，并按排序顺序打印值。
• 遍历涉及访问左子树，打印当前节点的值，然后访问右子树。

cartesianTreeSort 函数

• cartesianTreeSort 函数是笛卡尔树排序算法的入口点。它接受输入数组 arr 及其大小 n。
• 它调用 buildCartesianTree 来构建笛卡尔树，然后调用 inOrderTraversal 来打印排序后的序列。

主函数

在主函数中，定义了一个示例数组 arr：{5, 10, 40, 30, 28}。计算数组的大小，并使用数组及其大小调用 cartesianTreeSort。

程序打印排序后的序列，这是笛卡尔树排序算法的结果。

复杂度分析

时间复杂度分析

构建笛卡尔树（buildCartesianTree 函数）

该函数通过遍历每个元素一次来递归地构建笛卡尔树。

在递归函数的每一层，它都会处理固定数量的元素，包括查找最小值和创建节点等任务。

构建笛卡尔树所需的时间复杂度为O(n log n)，其中“n”表示输入数组中包含的元素数量。

中序遍历（inOrderTraversal 函数）

中序遍历访问每个节点一次。

中序遍历的时间复杂度为 O(n)，其中 n 是笛卡尔树中的节点数。

将构建笛卡尔树和执行中序遍历的时间复杂度相结合，笛卡尔树排序的总时间复杂度为O(n log n)。

空间复杂度分析

节点结构

输入数组中的每个元素对应笛卡尔树中的一个节点。存储这些节点所需的空间随数组中元素数量的增长而增长。

节点结构的空间复杂度为O(n)。

递归栈

buildCartesianTree 函数中的递归调用会消耗调用栈空间。

构建笛卡尔树所用递归的最大深度对应于树的高度。在最坏的情况下，笛卡尔树的高度为log(n)，其中 n 是输入数组中包含的元素数量。

由于递归栈造成的空间复杂度为O(log n)。

将节点结构和递归栈的空间复杂度相结合，笛卡尔树排序的总空间复杂度为O(n + log n)。

在实践中，主要因素是节点结构所需的空间，而递归栈的贡献相对较小。

方法二：带栈的迭代笛卡尔树排序

带栈的迭代笛卡尔树排序涉及使用迭代方法和栈数据结构来构建笛卡尔树。该方法避免了递归方法中常用的递归调用。栈用于在迭代过程中跟踪部分笛卡尔树。主要步骤包括节点构造、基于栈的树构造和用于排序的中序遍历。

程序

输出

Sorted Sequence: 5 10 40 30 28 

解释

节点构造

• 该算法通过迭代不重复数字的输入序列开始。
• 对于每个元素，都会创建一个相应的节点。该节点包含元素的（值、序列中的索引），并将左右指针初始化为 nullptr。

基于栈的树构造

• 在迭代过程中，使用一个栈（s）来维护部分笛卡尔树。对于每个节点，将其值与栈顶进行比较。
• 假设当前节点的值小于栈顶。在这种情况下，意味着当前节点应该是栈顶节点的左子节点，并且此过程会重复进行，直到找到当前节点的合适位置。
• 然后将当前节点推入栈中。

最终笛卡尔树

迭代完成后栈顶代表笛卡尔树的根。

用于排序的中序遍历

• 为了获得排序后的序列，算法会对笛卡尔树执行中序遍历。在遍历过程中，算法使用第二个栈（inOrderStack）来跟踪节点。
• 遍历从根开始，一直向左移动，直到到达最左边的节点。在此过程中，节点被推入 inOrderStack。
• 一旦到达最左边的节点，就将其从 inOrderStack 中弹出，打印其值，然后算法移动到其右子节点。此过程一直持续到处理完所有节点。

关键点

• 该算法使用栈有效地维护笛卡尔树结构，避免了递归调用。它利用栈在迭代过程中调整笛卡尔树的属性。
• 中序遍历确保从笛卡尔树中获得排序后的序列。
• 带栈的迭代笛卡尔树排序是一种高效的排序算法，它使用迭代方法、栈和笛卡尔树的属性对序列进行排序。它实现了线性时间和线性空间复杂度，使其成为一种实用的排序解决方案。

复杂度分析

时间复杂度

节点构造和栈操作

输入序列中的每个元素仅处理一次。对于每个元素，算法都会执行固定数量的栈操作。

考虑到节点构造和栈操作，总时间复杂度为O(n)，其中“n”表示输入序列中包含的元素数量。

中序遍历

中序遍历对笛卡尔树中的每个节点执行一次。

中序遍历的时间复杂度为O(n)，其中 n 是笛卡尔树中的节点数。

将节点构造、栈操作和中序遍历的复杂度相结合，带栈的迭代笛卡尔树排序的总时间复杂度为O(n)。

空间复杂度

节点结构

输入数组中的每个元素都代表笛卡尔树中的一个节点。存储这些节点所需的空间随数组中元素的数量而增长。

节点结构的空间复杂度为O(n)。

栈（s 和 inOrderStack）

该算法使用两个栈（s 用于树构造，inOrderStack 用于遍历）。

每个栈的最大大小与笛卡尔树的高度成正比，在最坏的情况下为 log(n)。

两个栈的空间复杂度均为O(log n)。

将节点结构和两个栈的空间复杂度相结合，带栈的迭代笛卡尔树排序的总空间复杂度为O(n + log n)。

在实践中，主要因素是节点结构所需的空间，而栈的贡献相对较小。

该算法效率很高，具有线性时间复杂度，适合排序大型数据集。空间复杂度也合理，算法在实践中表现良好。

方法三：使用线段树

使用线段树的笛卡尔树排序涉及高效查找范围内的最小元素。这种方法通过在输入数组的每个范围内选择最小元素来构建笛卡尔树。关键思想是使用线段树数据结构来高效地回答范围最小查询。

线段树概述

线段树是一种二叉树数据结构，用于存储有关区间或段的信息。

线段树的每个叶子节点代表输入数组中的一个元素。

每个非叶子节点存储其子节点的最小值。

使用线段树的笛卡尔树排序

节点结构

Node 代表笛卡尔树结构中的一个节点。每个节点包含最小值、该最小值的索引以及指向其左子节点和右子节点的指针或引用。

构建笛卡尔树

笛卡尔树是使用从线段树获得的最小值递归构建的。

在每一步中，通过利用线段树查询操作来确定当前范围内的最小元素和索引。然后使用此最小值和索引生成一个 Node。此过程依次对左子范围和右子范围进行。

线段树操作

构建

构建线段树以表示输入数组中不同子范围的最小值。

构建操作通常自底向上进行。

查询

查询操作用于查找给定范围内的最小元素及其索引。

它以对数时间有效地查找指定范围内的最小值。

中序遍历

构建笛卡尔树后，执行中序遍历以输出排序后的序列。

程序

输出

Sorted Sequence: 5 10 40 30 28

解释

节点结构（Node）

Node 结构表示笛卡尔树中的一个节点。

它包含三个重要属性：

value：表示范围内的最小值。

index：保存最小值的索引。

left 和 right：指向节点左右子节点的指针。

Build Cartesian Tree（buildCartesianTree）

此函数递归地构建笛卡尔树。关键操作是使用线段树查询在给定范围内查找最小值及其索引。

对于每个范围，都会创建一个带有最小值和索引的节点，并对左子范围和右子范围递归地调用该函数。

这确保了通过在每个范围内选择最小元素来构建笛卡尔树。

Build Segment Tree（buildSegmentTree）

此函数初始化并构建线段树。

它设置必要的数据结构，并调用 buildCartesianTree 函数来使用线段树创建笛卡尔树。

In-Order Traversal（inOrderTraversal）

• inOrderTraversal 函数对笛卡尔树执行中序遍历。
• 它按排序顺序打印元素，因为笛卡尔树的中序遍历会产生排序后的序列。

Cartesian Tree Sort（cartesianTreeSort）

• cartesianTreeSort 函数是使用线段树的笛卡尔树排序的入口点。
• 它调用必要的函数来初始化和构建线段树，构建笛卡尔树，并执行中序遍历进行排序。输出是输入序列的排序结果。

输出

程序的输出是使用线段树通过笛卡尔树排序获得的输入序列的排序结果。

• 使用线段树的笛卡尔树排序有效地结合了笛卡尔树和线段树的原理。
• 它利用线段树查找每个子范围内的最小值，构建一个内在代表输入序列排序顺序的笛卡尔树。
• 最终排序序列是通过执行笛卡尔树的中序遍历来实现的。

复杂度分析

时间复杂度

Build Cartesian Tree（buildCartesianTree）

构建操作涉及通过在每个范围内选择最小元素来构建笛卡尔树。

对于笛卡尔树中的每个节点，都会执行线段树查询以查找子范围内的最小值。

由于笛卡尔树中有 O(N) 个节点，因此构建笛卡尔树的总时间复杂度为O(N log N)。

Build Segment Tree（buildSegmentTree）

线段树的构建操作涉及初始化和构造树。

因此，构建线段树的总时间复杂度为O(N)。

In-Order Traversal（inOrderTraversal）

笛卡尔树的中序遍历是一个线性时间操作，因为每个节点都只访问一次。

中序遍历的时间复杂度为O(N)，其中 N 是笛卡尔树中的节点数。

Cartesian Tree Sort（cartesianTreeSort）

总时间复杂度主要由构建笛卡尔树决定，为 O(N log N)。

空间复杂度

节点结构（Node）

笛卡尔树中的每个节点都需要恒定的空间，因为它只存储几个变量（值、索引、左右子节点）。

每个节点所需的空间复杂度为O(1)。

Build Cartesian Tree（buildCartesianTree）

空间复杂度由笛卡尔树中的节点数决定。

由于笛卡尔树中有O(N)个节点，因此空间复杂度为O(N)。

Build Segment Tree（buildSegmentTree）

线段树的空间复杂度为O(4N)，因为线段树通常使用数组实现，对于 N 个元素，需要 4N 个节点。

每个节点存储有关输入数组中范围的信息。

In-Order Traversal（inOrderTraversal）

中序遍历所需的空间很小，通常为O(1)，因为它不使用随输入大小增长的附加数据结构。

Cartesian Tree Sort（cartesianTreeSort）

总空间复杂度主要由笛卡尔树决定，为O(N)。

结论

笛卡尔树排序是一种利用笛卡尔树数据结构的独特方法。该算法的优雅之处在于其将树构造与排序过程无缝集成。这种集成为排序不重复数字序列提供了一种高效且直观的方法。理解笛卡尔树背后的原理、它们的构造以及随后的中序遍历，可以深入了解笛卡尔树排序的理论基础和实际应用。