## True Story Follows

So in addition to the regular donation checks that get mailed to me from my supporters, I’ve gotten quite a few angry hate mails about a previous post about Skew Binomial Queues in Python. My goal for the exercise was to understand some non-conventional datastructures and make a contribution to society where variables were expressed as English words rather than variables more akin to mathematical equations. But as far as practicality went, it’s clear that there’s virtually no point in implementing a datastructure in Python. Even in Python, the core datastructures are implemented in C. Hence, people are angry with me and the trolls are out for blood.

I don’t want any more bloodshed. So I re-wrote skew binomial queues in Go so that we can soon reach the cusp of practicality.

## Performance in Go vs. Python

If you want to read about skew binomial queues, please check out my earlier post or if you want to read from an actual respected author, check out Chris Okasaki’s paper.

Otherwise, the interesting take-away with a re-write in Go is to see the performance differences. It’s also noteworthy that I spent 0 time trying to make performance optimizations, so it’s quite possible that I can still find some bottlenecks and crush them. The other thing to note is that with Go’s implementation, there were places at which I could no longer make things purely functional, and I had to introduce some assignment statements; I’m sure the boys down at Haight-Ashbury are going to have something to say about this.

Anyway, here are some quick measurements:

## Enqueue N Elements

 Number of Elements Seconds in Golang Seconds in Python 10,000 0.023 0.245 100,000 0.385 2.652 1,000,000 7.89 32.682

## Dequeue N Elements

 Number of Elements Seconds in Golang Seconds in Python 1,000 0.029 0.311 10,000 0.555 5.230 100,000 11.185 82.903

## Merge 2 Queues of N Elements

And just to be a weirdo, here’s merge!

 Number of Elements Seconds in Golang Seconds in Python 10,000 0.000000 0.000000 100,000 0.000000 0.000000

## The Code

```package skewBinomialQ

import (
"sort"
)

type QueuePriority interface {
LessThan(otherPriority QueuePriority) bool
}

func min(x, y QueuePriority) QueuePriority {
if x.LessThan(y) {
return x
}
return y
}

type Node interface {
Rank() int
Length() int
Children() []Node
Peek() QueuePriority
IsEmpty() bool
}

type NullObject struct {
children []Node
}

func (n NullObject) Link(heaps ...Node) Node {
return n
}

func (n NullObject) Peek() QueuePriority {
return nil
}

func (n NullObject) Children() []Node {
return n.children
}

func (n NullObject) Rank() int {
return -1
}

func (n NullObject) IsEmpty() bool {
return true
}

func (n NullObject) Length() int {
return 0
}

type SkewBinomialHeap struct {
rank     int
priority QueuePriority
children []Node
length   int
}

type skewByRank []SkewBinomialQueue

func (a skewByRank) Len() int           { return len(a) }
func (a skewByRank) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a skewByRank) Less(i, j int) bool { return a[i].Rank() > a[j].Rank() }

type byRank []Node

func (a byRank) Len() int           { return len(a) }
func (a byRank) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a byRank) Less(i, j int) bool { return a[i].Rank() < a[j].Rank() }

type byPriority []Node

func (a byPriority) Len() int           { return len(a) }
func (a byPriority) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a byPriority) Less(i, j int) bool { return a[i].Peek().LessThan(a[j].Peek()) }

func NewSkewBinomialHeap(priority QueuePriority) Node {
return SkewBinomialHeap{
priority: priority,
length:   1,
}
}

func highestPriorityHeap(heaps ...Node) Node {
sort.Sort(
byPriority(
heaps,
),
)
return heaps[0]
}

func lowerPriorityHeaps(heaps ...Node) []Node {
// TODO rename this to lowerRankedHeaps
sort.Sort(
byPriority(
heaps,
),
)
heaps = heaps[1:]
sort.Sort(
byRank(
heaps,
),
)
return heaps
}

func newNode(priority QueuePriority, rank int, children []Node) Node {
var existingLength int
for _, node := range children {
// TODO see if I can do this more elegantly?
existingLength += node.Length()
}
return SkewBinomialHeap{
rank:     rank,
priority: priority,
children: children,
length:   1 + existingLength,
}
}

func (s SkewBinomialHeap) IsEmpty() bool {
return false
}

func (s SkewBinomialHeap) Children() []Node {
return s.children
}

func (s SkewBinomialHeap) Link(heaps ...Node) Node {
heaps = append(heaps, s)
return newNode(
highestPriorityHeap(heaps...).Peek(),
heaps[len(heaps)-1].Rank()+1,
append(
lowerPriorityHeaps(heaps...),
highestPriorityHeap(heaps...).Children()...,
),
)
}

func (s SkewBinomialHeap) Length() int {
return s.length
}

func (s SkewBinomialHeap) Rank() int {
return s.rank
}

func (s SkewBinomialHeap) Peek() QueuePriority {
return s.priority
}

type SkewBinomialQueue struct {
rightSibling *SkewBinomialQueue
}

func NewEmptySkewBinomialQueue() SkewBinomialQueue {
return SkewBinomialQueue{
heapHead:     NullObject{}, // TODO see if there are performance benefits to making just 1 nullobject singleton
rightSibling: nil,
}
}

func newSkewBinomialQueue(heapHead Node, rightSibling *SkewBinomialQueue) SkewBinomialQueue {
return SkewBinomialQueue{
rightSibling: rightSibling,
}
}

func (q SkewBinomialQueue) firstTwoTreesEqualRank() bool {
return false
}
if q.rightSibling == nil {
return false
}
return q.Rank() == q.rightSibling.Rank()
}

func (q SkewBinomialQueue) Enqueue(priority QueuePriority) SkewBinomialQueue {
if q.firstTwoTreesEqualRank() {
// null checks should not be necessary here since first two trees are equal
return newSkewBinomialQueue(
),
q.rightSibling.rightSibling,
)
}
return newSkewBinomialQueue(
NewSkewBinomialHeap(priority),
&q,
)
}

func (q SkewBinomialQueue) Peek() QueuePriority {
return nil
}
if q.rightSibling == nil {
}
}
return min(
q.rightSibling.Peek(),
)
}

func (q SkewBinomialQueue) Meld(otherQ SkewBinomialQueue) SkewBinomialQueue {
if q.IsEmpty() {
return otherQ
} else if otherQ.IsEmpty() {
return q
}

allForests := append(q.asIndividualForests(), otherQ.asIndividualForests()...)
sort.Sort(
skewByRank(
allForests,
),
)
finalQ := new(SkewBinomialQueue)

*finalQ = NewEmptySkewBinomialQueue()

for _, qOneTree := range allForests {
// TODO avoid special casing this if I can
*finalQ = newSkewBinomialQueue(
nil,
)
} else if finalQ.Rank() == qOneTree.Rank() {
if finalQ.rightSibling == nil {
*finalQ = newSkewBinomialQueue(
nil,
)
} else {
*finalQ = finalQ.rightSibling.Meld(
newSkewBinomialQueue(
nil,
),
)
}
} else if qOneTree.Rank() < finalQ.Rank() {
newQ := newSkewBinomialQueue(
finalQ,
)
finalQ = new(SkewBinomialQueue)
*finalQ = newQ
} else {
*finalQ = newSkewBinomialQueue(
&qOneTree,
)
}
}
return *finalQ
}

func (q SkewBinomialQueue) Rank() int {
// TODO unsure if this method makes this unclear, but most use cases for checking
// rank involve cheaking the heap head
}

func (q SkewBinomialQueue) asIndividualForests() []SkewBinomialQueue {
if q.IsEmpty() {
return nil
} else if q.rightSibling == nil {
return []SkewBinomialQueue{q}
}
return append(
q.rightSibling.asIndividualForests()...,
)
}

func (q SkewBinomialQueue) Dequeue() (QueuePriority, SkewBinomialQueue) {
return nil, q
}
poppedQueue, remainingQueue := q.popHighestPriorityQueue()

var childrenRankGreaterThanZero []SkewBinomialQueue
var prioritiesRankZero []QueuePriority

for _, child := range poppedQueue.heapHead.Children() {
if child.Rank() > 0 {
childrenRankGreaterThanZero = append(
childrenRankGreaterThanZero,
newSkewBinomialQueue(
child,
nil,
),
)
} else {
prioritiesRankZero = append(
prioritiesRankZero,
child.Peek(),
)
}
}

finalQueue := remainingQueue
for _, queue := range childrenRankGreaterThanZero {
finalQueue = finalQueue.Meld(queue)
}
return poppedQueue.Peek(), finalQueue.bulkInsert(prioritiesRankZero...)
}

func (q SkewBinomialQueue) Length() int {
if q.rightSibling == nil || q.rightSibling.heapHead.IsEmpty() {
}
val2 := q.rightSibling.Length()
return val1 + val2
}

func (q SkewBinomialQueue) bulkInsert(priorities ...QueuePriority) SkewBinomialQueue {
if len(priorities) == 0 {
return q
}
return q.Enqueue(
priorities[0],
).bulkInsert(priorities[1:]...)
}

func (q SkewBinomialQueue) IsEmpty() bool {
}

func (q SkewBinomialQueue) popHighestPriorityQueue() (SkewBinomialQueue, SkewBinomialQueue) {
if q.rightSibling == nil {
return q, NewEmptySkewBinomialQueue()
}
return newSkewBinomialQueue(
nil,
),
*q.rightSibling
}
poppedQueue, remainingQueue := q.rightSibling.popHighestPriorityQueue()
}

type RootedSkewBinomialQueue struct {
highestPriorityObject QueuePriority
priorityQueue         SkewBinomialQueue
}

func NewEmptyRootedSkewBinomialQueue() RootedSkewBinomialQueue {
return RootedSkewBinomialQueue{
highestPriorityObject: nil,
priorityQueue:         NewEmptySkewBinomialQueue(),
}
}

func (r RootedSkewBinomialQueue) IsEmpty() bool {
return r.highestPriorityObject == nil
}

func (r RootedSkewBinomialQueue) Enqueue(priority QueuePriority) RootedSkewBinomialQueue {
if r.IsEmpty() {
return RootedSkewBinomialQueue{
highestPriorityObject: priority,
priorityQueue:         NewEmptySkewBinomialQueue(),
}
}
if r.highestPriorityObject.LessThan(priority) {
return RootedSkewBinomialQueue{
highestPriorityObject: r.highestPriorityObject,
priorityQueue:         r.priorityQueue.Enqueue(priority),
}
}
return RootedSkewBinomialQueue{
highestPriorityObject: priority,
priorityQueue: r.priorityQueue.Enqueue(
r.highestPriorityObject,
),
}
}

func (r RootedSkewBinomialQueue) Dequeue() (QueuePriority, RootedSkewBinomialQueue) {
if r.priorityQueue.IsEmpty() {
return r.highestPriorityObject, NewEmptyRootedSkewBinomialQueue()
}
highestPriorityObject, priorityQueue := r.priorityQueue.Dequeue()
return r.highestPriorityObject, RootedSkewBinomialQueue{
highestPriorityObject: highestPriorityObject,
priorityQueue:         priorityQueue,
}
}

func (r RootedSkewBinomialQueue) Meld(otherQ RootedSkewBinomialQueue) RootedSkewBinomialQueue {
mergedPrimitiveQueue := r.priorityQueue.Meld(otherQ.priorityQueue)
if r.highestPriorityObject.LessThan(otherQ.highestPriorityObject) {
return RootedSkewBinomialQueue{
highestPriorityObject: r.highestPriorityObject,
priorityQueue: mergedPrimitiveQueue.Enqueue(
otherQ.highestPriorityObject,
),
}
}
return RootedSkewBinomialQueue{
highestPriorityObject: otherQ.highestPriorityObject,
priorityQueue: mergedPrimitiveQueue.Enqueue(
r.highestPriorityObject,
),
}
}

func (r RootedSkewBinomialQueue) Peek() QueuePriority {
return r.highestPriorityObject
}

func (r RootedSkewBinomialQueue) Length() int {
if r.IsEmpty() {
return 0
}
return 1 + r.priorityQueue.Length()
}

type BootstrappedSkewBinomialQueue struct {
highestPriorityObject QueuePriority
priorityQueue         SkewBinomialQueue
length                int
}

func NewEmptyBootstrappedSkewBinomialQueue() BootstrappedSkewBinomialQueue {
return BootstrappedSkewBinomialQueue{
highestPriorityObject: nil,
priorityQueue:         NewEmptySkewBinomialQueue(),
length:                0,
}
}

func (b BootstrappedSkewBinomialQueue) IsEmpty() bool {
return b.highestPriorityObject == nil
}

func (b BootstrappedSkewBinomialQueue) Enqueue(priority QueuePriority) BootstrappedSkewBinomialQueue {
return b.Meld(
BootstrappedSkewBinomialQueue{
highestPriorityObject: priority,
priorityQueue:         NewEmptySkewBinomialQueue(),
length:                1,
},
)
}

func (b BootstrappedSkewBinomialQueue) Peek() QueuePriority {
return b.highestPriorityObject
}

func (b BootstrappedSkewBinomialQueue) Dequeue() (QueuePriority, BootstrappedSkewBinomialQueue) {
if b.priorityQueue.IsEmpty() || b.IsEmpty() {
return b.highestPriorityObject, NewEmptyBootstrappedSkewBinomialQueue()
}
queuePriority, updatedPrimitiveQueue := b.priorityQueue.Dequeue()
highestPriorityBootstrappedQueue, ok := queuePriority.(BootstrappedSkewBinomialQueue)

if !ok {
panic("Cannot cast to a Bootstrapped Queue. This case should not have been reached")
}
updatedBootstrappedQueue := BootstrappedSkewBinomialQueue{
highestPriorityObject: highestPriorityBootstrappedQueue.highestPriorityObject,
priorityQueue:         updatedPrimitiveQueue.Meld(highestPriorityBootstrappedQueue.priorityQueue),
length:                b.Length() - 1,
}
return b.highestPriorityObject, updatedBootstrappedQueue
}

func (b BootstrappedSkewBinomialQueue) Length() int {
return b.length
}

func (b BootstrappedSkewBinomialQueue) Meld(otherQ BootstrappedSkewBinomialQueue) BootstrappedSkewBinomialQueue {
if b.IsEmpty() {
return otherQ
} else if otherQ.IsEmpty() {
return b
} else if b.Peek().LessThan(otherQ.Peek()) {
return BootstrappedSkewBinomialQueue{
highestPriorityObject: b.Peek(),
priorityQueue: b.priorityQueue.Enqueue(
otherQ,
),
length: b.Length() + otherQ.Length(),
}
}
return BootstrappedSkewBinomialQueue{
highestPriorityObject: otherQ.Peek(),
priorityQueue: otherQ.priorityQueue.Enqueue(
b,
),
length: b.Length() + otherQ.Length(),
}
}

func (b BootstrappedSkewBinomialQueue) LessThan(otherPriority QueuePriority) bool {
otherQ, ok := otherPriority.(BootstrappedSkewBinomialQueue)
if ok {
if otherQ.IsEmpty() {
return true
} else if b.IsEmpty() {
return false
}
return b.Peek().LessThan(otherQ.Peek())
}
return false
}
```

## Usage

It’s this easy…

### Define a type in order to enqueue values

```package main

import (
"skewBinomialQ"
)

type IntegerQueuePriority struct {
value int
}

func (i IntegerQueuePriority) LessThan(otherPriority skewBinomialQ.QueuePriority) bool {
integerQueuePriority, ok := otherPriority.(IntegerQueuePriority)
if ok {
return i.value < integerQueuePriority.value
}
return false
}
```

### Example Enqueue Values

```q := skewBinomialQ.NewEmptyBootstrappedSkewBinomialQueue()
for _, number := range randomNumbers {
q = q.Enqueue(
IntegerQueuePriority{number},
)
}
```

### Example Meld 2 Queues

```q1 := skewBinomialQ.NewEmptyBootstrappedSkewBinomialQueue()
q1 = q1.Enqueue(IntegerQueuePriority{5})

q2 := skewBinomialQ.NewEmptyBootstrappedSkewBinomialQueue()
q2 := q2.Enqueue(IntegerQueuePriority{10})

// EXAMPLE MELD
q3 := q2.Meld(q1)
```

### Example Dequeue

```var value skewBinomialQ.QueuePriority

for {
value, q = q.Dequeue()
actual, ok := value.(IntegerQueuePriority)
if ok {
fmt.Printf("Value is %d\n", actual.value)
} else {
// reached empty queue
break
}
}
```