Leftist heaps

A search binary tree is defined by subclassing

CTBinaryTreeAbstract subclass: #CTLeftistHeap
	instanceVariableNames: ''
	classVariableNames: ''
	package: 'Containers-LeftistHeap'

and the corresponding test class defines,

"CTLeftistHeapTest, protocol tests"
tree: aCollection

   ^ aCollection asLeftistHeap

that uses

"Collection, protocol *Containers-LeftistHeap"
asLeftistHeap

   ^ self asBinaryTree: CTLeftistHeap

to show the following inspectors. First, the empty tree looks like

Second, we have the four cases:

• sorted data in arrayed collection,

  

  by means of

  "CTBinaryTreeNodeLeftistHeap, protocol actions"
  mergeBinaryTreeElement: aBTElement inBinaryTree: aBinaryTree
  
     ^ aBTElement ifEmpty: [ self ] ifNotEmpty: [ 
          | y |
          y := aBTElement value.
          ((aBinaryTree is: value lessThan: y) or: [ 
              aBinaryTree is: value equalTo: y ])
             ifTrue: [ 
                | r |
                r := nextLink
                        mergeBinaryTreeElement: aBTElement
                        inBinaryTree: aBinaryTree.
                self
                   insert: value
                   left: previousLink
                   right: r
                   inBinaryTree: aBinaryTree ]
             ifFalse: [ 
                | r |
                r := self
                        mergeBinaryTreeElement: aBTElement nextLink
                        inBinaryTree: aBinaryTree.
                self
                   insert: y
                   left: aBTElement previousLink
                   right: r
                   inBinaryTree: aBinaryTree ] ]
  

  and

  "CTBinaryTreeNodeLeftistHeap, protocol actions"
  insert: aValue left: leftHeap right: rightHeap inBinaryTree: aBinaryTree
  
     | v w t |
     v := leftHeap rank.
     w := rightHeap rank.
     (aBinaryTree is: v lessThan: w)
        ifTrue: [ 
           t := aBinaryTree
                   leftBinaryTreeElement: rightHeap
                   value: aValue
                   rightBinaryTreeElement: leftHeap.
           t rank: v + 1 ]
        ifFalse: [ 
           t := aBinaryTree
                   leftBinaryTreeElement: leftHeap
                   value: aValue
                   rightBinaryTreeElement: rightHeap.
           t rank: w + 1 ].
     ^ t
  

• sorted data in ordered collection,

  

• shuffled data in arrayed collection,

  

• shuffled data in ordered collection,