heap.dc (needed for day 8 part 1 dc sol'n)

[s.q] sQ
[+s.q] sX
[r]  sr

0 s0
1 s1
2 s2
3 s3
4 s4
_5 s_
_3 s-

# sort minmax indices
[
    dl3R dl3R ;hr;h            # a b -> h(b) h(a) b a
    <r                       #     -> (index of max) (index of min)
] s~

# heapify: sort heap (index ->)
[
    dddl2*                    # left index index index
    d lh !<~                 # max min(left, index) index index
    s.                       # clear max
    rl2*l1+                    # right min(left, index) index
    d lh !<~                 # max min(left, right, index) index
    s.                       # clear max

    dl3R dl3R                  # min index index min
    =X                       # clear stack and quit if no change

    r
    dl3R dl3R                  # min index index min
    ;hr;h                    # h(index) h(min) index min

    l4Rdl_R                   # min h(index) h(min) index min
    :hr:h                    # swap h(min) with h(index); min
    l@x                      # recurse on min index
] s@

# insert item (item ->)
[
    #[insert: ]np
    lh l1+ dsh                # ++end item
    dl-R :h                  # h(end) = item; end

    # stack: i = end
    [
        dl2/dd;h l4R d ;h l3R   # h(1/2) h(i) i i/2 i/2
        <X                   # parent less than child, done
        dl3R dl3R              # i i/2 i/2 i i/2
        ;hr;h                # h(i/2) h(i) i/2 i i/2
        l4R:h r:h             # swap h(i), h(i/2); i/2
        d l1<L
    ] dsLx
    s.
] s<

# get next (-> item) (doesn't check for empty)
[
    l1;h                     # item
    lh dl1- sh               # end--; end item
    d l1=Q                   # no items left after this, return item
    ;h l1:h                  # h(1) = h(end); item
    l1 l@x                   # sort heap from 1
] s>