Pop method for Brodal-Okasaki Heap

BO_Pop.go

func (bq *BOHeap) Pop() int {
	// Pop for Brodal-Okasaki Heap.
		// Root node is the return value.
		// If the root happens to have a subqueue, merge those nodes using ordinary binomial heap procedure.
		// Among the children of root, elect a new minimum node.
		// Merge the children of the new root according to skew binomial pop procedure.

	// Pop for skew binomial:
		// Remove the minimum root
		// Partition the gone roots children into 2 groups: Those with rank 0 and those with rank >0
		// Add the children with rank >0 by executing ordinary binomial heap merge procedure.
		// Add the children with rank 0 by executing insert procedure.
	retval := bq.root.value

	if bq.root.subqueue_head != nil {
		bq.merge_subqueue()
	}

	minchild := bq.root.getMinChildren()
	zrank, nzrank := minchild.partition()

	for _, znode := range zrank {
		znode.rogue()
		bq.insert(znode)
	}

	for _, nznode := range nzrank {
		nznode.rogue_hard()
		bq.merge_binomial(nznode)
	}

	minchild.rogue_hard()
	bq.promoteToRoot(minchild)

	return retval
}