Pairing Heaps

pairing.go

package heaps

// Elem is a comparable element of the heap
type Elem interface {
	Compare(elem Elem) int
}

// PairingHeap is a type of heap data structure
type PairingHeap struct {
	elem     Elem
	subheaps []*PairingHeap
}

// Empty returns true is a pairing heap is an empty heap, otherwise false.
func (ph *PairingHeap) Empty() bool {
	return nil == ph || nil == ph.elem
}

// FindMin returns the root element of the heap.
func (ph *PairingHeap) FindMin() Elem {
	if ph.Empty() {
		return nil
	}

	return ph.elem
}

// Merge - merging with an empty heap returns the other heap,
// otherwise a new heap is returned that has the minimum of the two root elements
// as its root element and just adds the heap with the larger root
// to the list of subheaps.
func (ph *PairingHeap) Merge(heap *PairingHeap) *PairingHeap {
	if ph.Empty() {
		return heap
	}

	if heap.Empty() {
		return ph
	}

	switch cmp := ph.elem.Compare(heap.elem); true {
	case cmp < 0:
		return &PairingHeap{elem: ph.elem, subheaps: append([]*PairingHeap{heap}, ph.subheaps...)}

	case cmp >= 0:
		return &PairingHeap{elem: heap.elem, subheaps: append([]*PairingHeap{ph}, heap.subheaps...)}
	}

	return nil
}

// Insert merges the heap with a new heap containing just this element
// and an empty list of subheaps.
func (ph *PairingHeap) Insert(elem Elem) *PairingHeap {
	heap := &PairingHeap{elem: elem}
	return heap.Merge(ph)
}

// DeleteMin first merges the subheaps in pairs
// (this is the step that gave this datastructure its name) from left to right
// and then merges the resulting list of heaps from right to left.
func (ph *PairingHeap) DeleteMin() *PairingHeap {
	if ph.Empty() {
		return ph
	}

	return mergePairs(ph.subheaps)
}

// mergePairs
func mergePairs(subheaps []*PairingHeap) *PairingHeap {
	switch n := len(subheaps); true {
	case n == 0:
		return &PairingHeap{}

	case n == 1:
		return subheaps[0]

	case n > 1:
		return (subheaps[0].Merge(subheaps[1])).Merge(mergePairs(subheaps[2:]))
	}
	return nil
}

pairing_test.go

package heaps

import (
	"fmt"
	"strconv"
	"strings"
	"testing"
)

type IntElem int

func (i IntElem) Compare(e Elem) int {
	return int(i) - int(e.(IntElem))
}

func (i IntElem) String() string {
	return strconv.Itoa(int(i))
}

func TestEmpty(t *testing.T) {
	var ph *PairingHeap
	if !ph.Empty() {
		t.FailNow()
	}

	ph = &PairingHeap{}
	if !ph.Empty() {
		t.FailNow()
	}

	ph.elem = IntElem(123)
	if ph.Empty() {
		t.FailNow()
	}
}

func TestInsertFindMinDeleteMin(t *testing.T) {
	var ph *PairingHeap
	if !ph.Empty() {
		t.FailNow()
	}

	ph = ph.
		Insert(IntElem(5)).
		Insert(IntElem(2)).
		Insert(IntElem(1)).
		Insert(IntElem(4)).
		Insert(IntElem(6)).
		Insert(IntElem(3)).
		Insert(IntElem(0)).
		Insert(IntElem(7)).
		Insert(IntElem(10)).
		Insert(IntElem(9)).
		Insert(IntElem(8))
	for min := 0; !ph.Empty(); min++ {
		println(ph, t)
		e := ph.FindMin().(IntElem)
		if e.Compare(IntElem(min)) != 0 {
			t.Fatalf("FindMin - actual: %d, expected: %d\n", e, min)
		}

		ph = ph.DeleteMin()
	}
}

func println(ph *PairingHeap, t *testing.T) {
	sb := &strings.Builder{}
	var build func(h *PairingHeap, tab int)
	build = func(h *PairingHeap, tab int) {
		sb.WriteString(strings.Repeat(".", tab))
		sb.WriteString(fmt.Sprintf("(%v):\n", h.elem))
		for _, sh := range h.subheaps {
			build(sh, tab+1)
		}
		sb.WriteString(strings.Repeat(".", tab))
		sb.WriteRune('\n')
	}
	build(ph, 0)
	t.Logf("--\n%s\n", sb.String())
}