Go: package Pairing heap

heap.go

package heap

type Node struct {
	Order
	tails
}

type Order interface {
	Ord(*Node) bool
}

type tails []*Node

func New(x Order) *Node {
	return &Node{Order: x}
}

func Merge(x, y *Node) (answer *Node) {
	switch {
	case x == nil:
		answer = y
	case y == nil:
		answer = x
	case x.Ord(y):
		answer = x
		answer.push(y)
	case !x.Ord(y):
		answer = y
		answer.push(x)
	}
	return
}

func (x *Node) Pop() *Node {
	return x.pair().fold()
}

func (x *tails) push(y *Node) {
	*x = append(*x, y)
}

func (x tails) pair() (answer tails) {
	half := len(x) / 2
	answer = make(tails, half)
	for i := 0; i < half; i++ {
		answer[i] = Merge(x[2*i], x[2*i+1])
	}
	if len(x)%2 != 0 {
		answer = append(answer, x[len(x)-1])
	}
	return
}

func (x tails) fold() (answer *Node) {
	for i := range x {
		answer = Merge(answer, x[i])
	}
	return
}