如何在配对堆中实现重复值元素的FIFO弹出顺序？

当前实现细节 #

• Push：O(1) 时间复杂度
• Pop：O(lgN) 时间复杂度
• Erase：O(lgN) 时间复杂度
• Decrease Key：O(lgN) 时间复杂度

优先队列元素结构定义：

struct pq_elem
{
    struct pq_elem *left_child;
    struct pq_elem *next_sibling;
    struct pq_elem *prev_sibling;
    struct pq_elem *parent;
};

树结构采用Fredman等人在配对堆原始论文第125页图14中的环形表示，额外添加了双向链表以支持快速erase和decrease key操作。

核心问题 #

是否存在一种合并与配对技术，可确保优先队列中具有重复值的元素按先进先出（FIFO）顺序弹出？需提供伪代码。

测试用例 #

推入元素（vl为键值，id标识推入/弹出顺序）：

|id 0| |id 1| |id 2| |id 3| |id 4| |id 5|
|vl 1| |vl 9| |vl 1| |vl 9| |vl 1| |vl 9|

理想弹出顺序：

|id 0| |id 2| |id 4| |id 1| |id 3| |id 5|
|vl 1| |vl 1| |vl 1| |vl 9| |vl 9| |vl 9|

实际弹出顺序：

|id 0| |id 2| |id 4| |id 5| |id 1| |id 3|
|vl 1| |vl 1| |vl 1| |vl 9| |vl 9| |vl 9|

Push阶段新元素作为父节点左子节点保留了顺序，但delete min操作的配对阶段打乱了重复值元素的顺序，需要解决方案保证重复值按FIFO弹出。

解决方案 #

要实现重复键值的FIFO顺序，核心是在比较键值时，若键值相等则比较元素的插入时间戳（即id），同时调整配对堆的合并逻辑，确保合并时不仅考虑键值大小，还考虑插入顺序。

修改后的元素结构（需添加时间戳） #

struct pq_elem
{
    struct pq_elem *left_child;
    struct pq_elem *next_sibling;
    struct pq_elem *prev_sibling;
    struct pq_elem *parent;
    int val;          // 原键值vl
    int timestamp;    // 插入顺序id，用于FIFO排序
};

比较函数定义 #

function compare(a, b):
    if a.val != b.val:
        return a.val < b.val  // 小顶堆逻辑，大顶堆可反转判断
    else:
        return a.timestamp < b.timestamp  // 键值相等时，插入早的优先级更高

调整配对堆的合并逻辑 #

配对堆的合并操作需基于上述比较函数，确保合并时始终将优先级更高的树作为父节点。

合并两个配对堆的伪代码

function merge(heap1, heap2):
    if heap1 is null:
        return heap2
    if heap2 is null:
        return heap1
    // 用自定义比较函数判断优先级
    if compare(heap2, heap1):
        // heap2优先级更高，将heap1作为heap2的左子节点
        heap1.prev_sibling = heap2
        heap1.next_sibling = heap2.left_child
        if heap2.left_child is not null:
            heap2.left_child.prev_sibling = heap1
        heap2.left_child = heap1
        heap1.parent = heap2
        return heap2
    else:
        // heap1优先级更高，将heap2作为heap1的左子节点
        heap2.prev_sibling = heap1
        heap2.next_sibling = heap1.left_child
        if heap1.left_child is not null:
            heap1.left_child.prev_sibling = heap2
        heap1.left_child = heap2
        heap2.parent = heap1
        return heap1

调整Delete Min后的配对阶段 #

在delete min操作后，需将根节点的所有子节点按原始插入顺序收集，再两两配对合并，最终合并成新堆，确保重复键值的顺序不被打乱。

Delete Min伪代码

function delete_min(heap):
    if heap is null:
        return null
    // 保存要弹出的最小值节点
    min_node = heap
    // 按从左到右顺序收集根节点的所有子节点，断开与原根的连接
    children = []
    current = heap.left_child
    while current is not null:
        next_node = current.next_sibling
        current.parent = null
        current.prev_sibling = null
        current.next_sibling = null
        children.append(current)
        current = next_node
    // 两两配对合并子节点，保持原始顺序
    merged_children = []
    i = 0
    while i < len(children):
        if i+1 < len(children):
            merged = merge(children[i], children[i+1])
            merged_children.append(merged)
            i += 2
        else:
            merged_children.append(children[i])
            i += 1
    // 合并所有配对后的堆，生成新的根节点
    new_heap = null
    for child in merged_children:
        new_heap = merge(new_heap, child)
    return (min_node, new_heap)

关键说明 #

1. 时间戳的必要性：通过为每个元素添加插入时间戳，将重复键值的比较转化为时间戳的比较，从根源上保证FIFO顺序。
2. 合并逻辑一致性：所有合并操作（包括Push时的合并和Delete Min后的配对合并）都必须使用包含时间戳的比较函数，确保优先级判断统一。
3. 子节点顺序保留：收集根节点子节点时按原始插入顺序操作，避免打乱重复元素的先后关系。

内容的提问来源于stack exchange，提问作者Alex Lopez