左式树 / 左式堆

引言

优先队列是左倾堆或左倾树。它使用二叉堆的变体构建。对于每个节点，我们存储到该节点锚定的子树中最近叶子的距离。我们称此值为 s-value。与总是完全二叉树的二叉堆相比，左倾堆极力趋向于高度不平衡。

堆是一种基于树的数据结构，其中优先级最高或最低的元素始终保留在树的“根”处。

堆是完全二叉树，其中除最后一层外，所有层都必须完全填充。它也是左对齐的，这意味着在填充右子树之前先填充左子树。

为了保证对数性能，整个二叉树会不断进行平衡。

关于堆最普遍的误解是它们是已排序的。然而，它们只是“部分排列”的，而不是已排序的。此外，每个级别的子节点之间没有相互关系。

前缀和在每个元素处都保持大于零的最长子序列的长度

引言

此问题的目标是找到一个最长子序列，其中每个元素的前缀和都大于零。该方法采用了 MinHeap，这是一个广泛使用且有用的数据结构。这篇博文将帮助您巩固对 Min Heap 数据结构的理解。

问题陈述

给定一个元素数组，确定一个前缀和在每个元素处都大于零的最短子序列的长度。

案例研究

为了更好地理解情况，请考虑两个测试用例。

测试用例 1

给定数组的输出是 4。

测试用例 2

给定数组的输出是 3。

注意：在此问题中，我们必须确定最长子序列和最长子数组的长度。子序列是从原始序列中删除一个或多个组件生成的给定序列的非连续序列。

方法

将使用 Min Heap 数据结构来解决此问题。我们将遍历数组并将每个条目放入最小堆中。我们还将一个元素添加到 sum 变量中，该变量将跟踪当前元素的总和。

如果总和变为负数，我们将从堆中减去最负的元素，然后从堆中弹出相关元素。

算法步骤

1. 获取用户的向量输入。
2. 使用优先队列创建一个空的最小堆。
3. 将 sum 变量设置为 0。
4. 从 0 到 n（向量的大小）运行一个 for 循环。
5. 将当前向量元素的值添加到 sum。
6. 将当前向量元素添加到最小堆。
7. 检查总数是否变为负数。

输出

最长子序列的长度为：4

• 复杂度分析

时间复杂度

O(n*logn)，因为我们迭代了一个“n”次的 for 循环。优先队列的 push 和 pop 操作需要 O(logn) 时间，因此总体时间复杂度为 O(n*logn)。数字 n 指的是输入向量中的项目总数。

空间复杂度

O(n)，因为我们使用的是大小为 n 的优先队列。数字 n 指的是输入向量中项目的数量。

测试用例的详细运行

为了进一步理解问题，请考虑测试用例 1 的详细运行。

输入的数组是，

-1, 6, 7, -15, -3, -1

起初，sum = 0，Min Heap 也是空的。

-1 被添加到 Min Heap，sum = -1。

然而，由于总数变为负数，我们从堆中移除了顶部元素。

下一个元素 6 被添加到堆中，因此总和为 6。

然后检查向量的下一个成员 7。当前总和为 13 (6+7)。因此，7 也被插入到堆中。

下一个元素是 -15，将其添加后，总数变为负数。

元素总和变为 -2，因此我们再次弹出堆的顶部元素 -15。

我们还从总数中减去 -15，使总数变为 13。

向量中的下一个成员是 -3；将其添加到最终总数中得到 10，这是一个正数。因此，它也被添加到堆中。

我们最终到达向量中的最后一个元素 -1，并将其添加到当前总数中。它也被放入堆中。

所以当前的 sum 是 9，我们的 Min Heap 将显示如下

最后，我们的 Min Heap 的大小是 4，这代表了最大子序列的长度。

堆的类型

堆主要有两种类型：

最小堆

在最小堆中，根节点表示树中所有节点中最小的，因为每个父节点的值始终小于或等于其子节点的值。

最大堆

在最大堆中，所有根节点的值是树中所有节点中最大的，并且每个父节点的值始终大于或等于其子节点的值。

二叉堆的表示

二叉堆占用的空间很小，并且易于在数组中表示。在算法中对二叉堆进行建模时，我们应牢记以下几点：

在数组中

请看以下示例

因为上面显示的二叉树是完全的，所以我们可以将其表示为数组如下：

因此，我们从第 0 层开始，即元素“10”，并用数组的第一个元素填充它，然后再递增指针。我们现在在第 1 层，我们将用此层的第一个子节点，即数字“9”，来填充数组，然后再移动到数字“8”。

类似地，我们将从第 2 层的第一个成员开始，并相应地填充我们的数组。

二叉堆遵循层序遍历，这意味着在进入下一层之前，会访问该层上的每个节点。使用此方法，二叉堆可以轻松地存储在数组中。

二项堆实现

操作

二叉堆可用于多种操作，其中一些如下所述：（请注意，下面概述的操作均以最大堆的术语给出。）

1. maxHeapify()

MaxHeapify 是负责恢复最大堆属性的程序。它安排节点 i 及其子树，以便保留堆属性。

以下步骤将详细解释该函数：

• 假设我们有一个名为 'ARR' 的数组，该数组表示整个二叉树。
• 我们将当前元素的索引“i”设置为“LARGEST”。
• 如果 ARR[2 * i + 1] > ARR[i]，这表示左子节点大于当前值，则该值设置为“LARGEST”。
• 类似地，如果 ARR[2 * i + 2] > ARR[i]，这表示右子节点大于当前值，则将其标记为“LARGEST”。
• 用当前元素替换“LARGEST”元素。
• 重复步骤 1-4，直到堆属性恢复为止。
• 让我们使用一个示例来练习前面的步骤。

2. insertKey()

在插入期间，新元素被附加到堆的末尾并成为数组的最后一个元素。如果新添加的元素小于父节点，则无需执行任何操作。否则，将交换值直到堆属性恢复。

3. increaseKey()

它将特定索引处的键的值增加到某个值。如果此新值小于父节点，则无需执行任何操作。否则，将违反堆属性，并进行交换以恢复它。

4. getMax()

返回最大堆的底部节点中存储的最大元素。

6. deletekey()

首先使用 increaseKey() 将要删除的元素替换为正无穷大，然后调用 removeMax() 将其从堆中删除。

下面的代码描绘了上述操作。

输入

输出

The current size of the heap is 7.
The current maximum element is 14.
The current size of the heap is 6.
The current size of the heap is 8.
The current maximum element is 15.

时间复杂度

下一节讨论二叉堆函数的各种时间复杂度。

构建时间

构建堆通常需要 O(N) 时间。可以使用级数收敛来证明这一点。

插入

将新键插入堆需要 heapify() 操作，需要 O(log (N)) 时间来恢复树的顺序，因为树的高度是 O(log (N))。因此，插入额外键的时间复杂度为 O(log (N))。

删除

删除根节点或键值后，需要对堆进行 heapify 以恢复树的属性。因此，复杂度也给出为 O (log N)。

获取最小或最大元素：根节点存储最小或最大元素。因此，它可以在一次操作中检索，其时间复杂度为 O(1)。

提取最小/最大元素：由于此操作在提取根元素后需要调用 heapify() 以恢复堆的属性，因此时间复杂度为 O(log(N))。

应用

二叉堆的一些最重要应用是：

• 在操作系统中用于优先处理作业调度。
• Dijkstra 算法（用于查找最短路径）、最小生成树和
• Prim's 算法使用它。
• 它用于执行堆排序。
• 使用此方法实现优先队列。

二叉堆的其他应用

• 尽管堆是相对灵活的数据结构，但内存分配通常非常快。与其他数据结构相比，元素添加和删除也相对较快。
• 由于最小值和最大值通常存储在根节点，因此也可以快速找到它们。
• 在嵌套列表和数组等数据结构中访问最小或最大元素需要 O(N) 时间。而二叉堆可以在仅 O(1) 时间内检索最小或最大元素，因为最大或最小元素始终位于根节点，我们只需要返回数组的第 0 个位置的元素。

时间复杂度

以下是左倾堆上若干操作的时间复杂度：

性质

左倾堆具有以下属性：

• Key(i) >= Key(parent(i))：这与普通的最小堆属性相当。
• 每个节点的右后代具有较低的 s-value。这表示从节点到右子节点最近叶子的最短路径上的边数之和小于或等于左子节点。

我们可以从上述属性推断出：

• 从根到最右叶子的路径上任何叶子到其底部的最短路径是运行的路径。
• 如果从根到最右叶子的路径中有 'X' 个节点，则左倾堆将包含至少 (2x-1) 个节点。
• 对于具有 N 个节点的左倾堆，从根到最左叶子的路径长度也为 O (logN)。

操作

merge()： merge 操作是左倾堆的主要操作。

deleteMin() 可用于用左右子树的合并替换最小节点。

insert()： 这是通过对初始堆和新的单节点堆执行 merge 方法来完成的。

S-value 或 Dist

节点的 s-value（或 dist）表示该节点与该节点子树中最近叶子之间的距离。空子节点的 dist 为 0（在某些实现中，空子节点的 dist 假定为 -1）。

合并

由于左倾堆的右子树比左子树小，我们将其与另一个树合并。