弱堆及其相关数据结构的性能分析与实验研究

### 弱堆及其相关数据结构的性能分析与实验研究 #### 1. 基本堆操作与框架设计 在堆操作中，插入元素时，需要将元素向上筛选，直至恢复半堆序。减少元素值时，从值改变的节点开始，将变化向上传播。删除元素时，把最后位置的元素移到被删除元素的位置，然后像删除最小值那样向下筛选，再像减少元素值那样向上筛选。 在框架设计方面，采用可调整大小的数组而非链表表示。为确保迭代器始终有效，间接存储元素，并维护数组与元素之间的指针。可调整大小的数组在增长和收缩操作的最坏情况下运行时间可保持恒定。通过接受不同的堆化策略，能轻松在弱堆和不同实现的二叉堆之间切换。 #### 2. 多堆框架 为改进插入操作的最坏情况，维护一系列完美弱堆，而非将所有元素放在单个堆中。由于子堆重定位频繁，采用基于指针的表示。 - **堆存储的基本操作**：堆存储支持注入（将新堆插入堆存储）和弹出（从堆存储中移除最小堆）操作。注入时，新堆的大小不能大于当前弱队列中最小堆的大小。 - **堆数量的控制**：删除最小值后，需遍历堆来确定包含新最小值的根，因此要控制堆的数量。最坏情况下，堆的最小数量为 ⌊lg n⌋ + 1。当新堆到来时，偶尔需要合并堆。 - **堆存储的实现策略** - **二进制数系统**：若弱队列存储 n 个元素，n 的二进制表示为 ⟨b0, b1, ..., b⌊lg n⌋⟩，则堆存储包含大小为 2i 的堆当且仅当 bi = 1。但此方法有时注入操作需执行对数级别的合并。 - **冗余二进制数系统**：若 di 表示高度为 i 的堆的数量，且 di ∈ {0, 1, 2}，堆存储可使基数序列 ⟨d0, d1, ..., d⌊lg n⌋⟩ 保持规则。每次注入后合并前两个相同大小的堆，可保持基数序列的规则性，且堆的数量不会超过 ⌊lg n⌋ + 1。 下面是多堆框架操作的流程图： ```mermaid graph TD A[开始] --> B{新堆到来?} B -- 是 --> C{新堆大小 <= 最小堆大小?} C -- 是 --> D[注入新堆] D --> E{是否需要合并堆?} E -- 是 --> F[合并堆] E -- 否 --> G[结束] C -- 否 --> G[结束] B -- 否 --> H{执行删除最小值操作?} H -- 是 --> I[遍历堆找新最小值] I --> J[移除最小堆] J --> G[结束] H -- 否 --> G[结束] ``` #### 3. 节点实现与堆存储类型 在节点实现方面，基线版本中每个节点存储一个元素以及指向其左子节点、右子节点和父节点的指针。为降低节点交换成本，尝试了间接存储元素的变体，但速度比基线版本慢。极端情况下，每个节点只需两个指针来处理父子关系，但这种空间优化并未带来性能提升。 框架支持两种类型的堆存储： - 为每个堆维护一个代理，并将这些代理保存在链表中。 - 重用节点上的指针，将根节点保存在链表中。同时，堆的高度通过位向量维护，可存储在一个字中。 这两种堆存储类型都可配备二进制数系统或冗余二进制数系统。对于冗余系统，采用预分配栈存储指向每对相同大小堆的第一个成员的指针是较好的选择。 #### 4. 删除策略对比 处理删除操作有两种策略： - **自上而下策略**：将被删除的节点筛选到根，然后移除根。 - **自下而上策略**：为被删除的节点找到替换节点，进行替换，然后对新节点进行向下或向上筛选。 在典型情况下，若不删除最小值，自下而上策略的工作量为 O(1)，而自上而下策略的工作量为对数级。 #### 5. 松弛堆框架 在松弛弱队列中，减少操作导致的半序违反通过标记解决。当标记节点过多时，减少标记节点的数量。 - **标记存储的操作**：用于跟踪所有标记的数据结构称为标记存储，支持标记（标记节点）、取消标记（移除标记）和减少（移除一个或多个未指定标记）操作。 - **节点的分类**：所有节点分为四类：未标记节点、成员、领导者和单例。 - **节点状态