Bootstrapped Skew Binomial Queues in Golang

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
  Link(heaps ...Node) Node
  IsEmpty() bool
}

type NullObject struct {
  head     *NullObject
  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 {
  heapHead     Node
  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{
    heapHead:     heapHead,
    rightSibling: rightSibling,
  }
}

func (q SkewBinomialQueue) firstTwoTreesEqualRank() bool {
  if q.heapHead.IsEmpty() {
    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(
      NewSkewBinomialHeap(priority).Link(
        q.heapHead,
        q.rightSibling.heapHead,
      ),
      q.rightSibling.rightSibling,
    )
  }
  return newSkewBinomialQueue(
    NewSkewBinomialHeap(priority),
    &q,
  )
}

func (q SkewBinomialQueue) Peek() QueuePriority {
  if q.heapHead.IsEmpty() {
    return nil
  }
  if q.rightSibling == nil {
    return q.heapHead.Peek()
  }
  if q.rightSibling.heapHead.IsEmpty() {
    return q.heapHead.Peek()
  }
  return min(
    q.heapHead.Peek(),
    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 {
    if finalQ.heapHead.IsEmpty() {
      // TODO avoid special casing this if I can
      *finalQ = newSkewBinomialQueue(
        qOneTree.heapHead,
        nil,
      )
    } else if finalQ.Rank() == qOneTree.Rank() {
      if finalQ.rightSibling == nil {
        *finalQ = newSkewBinomialQueue(
          finalQ.heapHead.Link(qOneTree.heapHead),
          nil,
        )
      } else {
        *finalQ = finalQ.rightSibling.Meld(
          newSkewBinomialQueue(
            finalQ.heapHead.Link(qOneTree.heapHead),
            nil,
          ),
        )
      }
    } else if qOneTree.Rank() < finalQ.Rank() {
      newQ := newSkewBinomialQueue(
        qOneTree.heapHead,
        finalQ,
      )
      finalQ = new(SkewBinomialQueue)
      *finalQ = newQ
    } else {
      *finalQ = newSkewBinomialQueue(
        finalQ.heapHead,
        &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
  return q.heapHead.Rank()
}

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

func (q SkewBinomialQueue) Dequeue() (QueuePriority, SkewBinomialQueue) {
  if q.heapHead.IsEmpty() {
    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() {
    return q.heapHead.Length()
  }
  val1 := q.heapHead.Length()
  val2 := q.rightSibling.Length()
  return val1 + val2
  return q.heapHead.Length() + q.rightSibling.Length()
}

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 {
  return q.heapHead.IsEmpty()
}

func (q SkewBinomialQueue) popHighestPriorityQueue() (SkewBinomialQueue, SkewBinomialQueue) {
  if q.rightSibling == nil {
    return q, NewEmptySkewBinomialQueue()
  }
  if q.rightSibling.heapHead.IsEmpty() || q.heapHead.Peek().LessThan(q.rightSibling.Peek()) {
    return newSkewBinomialQueue(
        q.heapHead,
        nil,
      ),
      *q.rightSibling
  }
  poppedQueue, remainingQueue := q.rightSibling.popHighestPriorityQueue()
  return poppedQueue, newSkewBinomialQueue(q.heapHead, &remainingQueue)
}

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
  }
}