APL implementation of a leftist tree

leftist.dyalog

⍝ APL implementation of a leftist tree.
⍝ 
⍝ https://en.wikipedia.org/wiki/Leftist_tree
⍝ http://typeocaml.com/2015/03/12/heap-leftist-tree/

⎕io←0
Insert←{ ⍝ Insert item into leftist tree, returning the resulting tree
    (tree item)←⍵
    1 item ⍬ ⍬ Merge tree 
}

Pop←{ ⍝ Pop off smallest element from a leftist tree
    0=≢⍵:⍬
    (v l r)←1↓⍵                 ⍝ value left right
    (l Merge r) v               ⍝ Return the resulting tree and the value
}

Merge←{ ⍝ Merge two leftist trees, t1 and t2
    t1←⍺ ⋄ t2←⍵
    0=≢t1:t2 ⋄ 0=≢t2:t1                          ⍝ If either is a leaf, return the other
    (key1 left right)←1↓t1 ⋄ key2←1⌷t2
    key1>key2:t2∇t1                              ⍝ Flip order to ensure smallest is root of merged
    merged←right∇t2                              ⍝ Merge rightwards
    (⊃left)≥⊃merged:(1+⊃merged) key1 left merged ⍝ Right is shorter
    (1+⊃left) key1 merged left                   ⍝ Left is shorter; make it the new right
}

Priority queue/heap implemented as a Leftist Tree

A tree is a vector containing nodes of the type

node←node_rank value left_tree right_tree

for the example given in the ocaml implementation: http://typeocaml.com/2015/03/12/heap-leftist-tree/ :

      h←Insert ⍬ 2
      h←Insert h 10
      h←Insert h 9
      s←Insert ⍬ 3
      s←Insert s 6
      h Merge s
┌→─────────────────────────────────────────────────────────────┐
│     ┌→────────────────────────────────────┐ ┌→─────────────┐ │
│ 2 2 │     ┌→────────────┐ ┌→────────────┐ │ │      ┌⊖┐ ┌⊖┐ │ │
│     │ 2 3 │     ┌⊖┐ ┌⊖┐ │ │     ┌⊖┐ ┌⊖┐ │ │ │ 1 10 │0│ │0│ │ │
│     │     │ 1 6 │0│ │0│ │ │ 1 9 │0│ │0│ │ │ │      └~┘ └~┘ │ │
│     │     │     └~┘ └~┘ │ │     └~┘ └~┘ │ │ └∊─────────────┘ │
│     │     └∊────────────┘ └∊────────────┘ │                  │
│     └∊────────────────────────────────────┘                  │
└∊─────────────────────────────────────────────────────────────┘