5C.md

配对堆

　　对于堆而言，最重要的其实是处理有序列的汇流。从上一节我们可以看到，堆的合并是处理汇流的关键。

　　二项堆中子树的合并只有O(1)的时间开销，我们可以在上面做些文章。首先是要打破2^k的节点数限制，允许一棵树拥有任意数目的节点。其次，为了便于节点的删除，还增加了前向指针。

type Node[T constraints.Ordered] struct {
    key   T
    child *Node[T]
    prev  *Node[T]  //父兄节点
    next  *Node[T]  //弟节点
}

我们放弃结构的工整性，获得了复杂度为O(1)的合并操作：

func merge[T constraints.Ordered](master, slave *Node[T]) *Node[T] {
    if master.key > slave.key {
        master, slave = slave, master
    }
    slave.next = slave.hook(master.child)
    master.child, slave.prev = slave, master
    return master
}

得过且过

和二项堆一样，配对堆的压入也是并入一个单元素堆。

当要修改某个节点的值时，可以分离此以节点为根的子堆，然后重新并入。

func (hp *Heap[T]) FloatUp(node *Node[T], value T) {
    if node != nil && value < node.key {        //只能单向修改，对最小堆而言是改小
        node.key = value
        if super := node.prev; super != nil && super.key > value {
            node.prev = nil
            if super.next == node {             //super为兄
                super.next, node.next = super.hook(node.next), nil
            } else {                            //super为父
                super.child, node.next = super.hook(node.next), nil
            }
            hp.root = merge(hp.root, node)
}   }   }

这些都只需要O(1)的时间，但是会使堆的存储结构变得混乱，从而需要整理。

奋起直追

出来混迟早还是要还的。删除节点之后，我们必须把其留下的子堆重新组织起来，才能并入原堆。

我们可以采用两两配对的方法在O(N)的时间内完成整理。

func collect[T constraints.Ordered](head *Node[T]) *Node[T] {
    if head != nil {
        for head.next != nil {
            list, knot := head, fakeHead(&head)
            for list != nil && list.next != nil {       //两两配对
                master, slave := list, list.next
                list = slave.next
                knot.next = merge(master, slave)
                knot = knot.next
            }
            knot.next = list
        }
        head.prev = nil
    }
    return head
}

也可以采用先配对再右向聚拢的的策略，这对像二项堆那样工整的序列更为有效。

func collect[T constraints.Ordered](head *Node[T]) *Node[T] {
    if head != nil && head.next != nil {
        list, last := head, fakeHead(&head)
        for list != nil && list.next != nil {           //两两配对
            master, slave := list, list.next
            list = slave.next
            last.next = last.hook(merge(master, slave))
            last = last.next
        }
        head.prev = nil
        if list == nil {
            head, list = last, last.prev
        } else {
            head, list = list, last
        }
        for list != nil {                               //向右聚拢
            last, list = list, list.prev
            head = merge(head, last)
        }
        head.prev, head.next = nil, nil
    }
    return head
}

实际上，整理操作只有最坏情况下的复杂度才到O(N)，其平均复杂度是O(logN)级的。

---

目录　上一节　下一节