 GENERIC: heap-push* ( value key heap -- entry )
 GENERIC: heap-peek ( heap -- value key )
 GENERIC: heap-pop* ( heap -- )
-GENERIC: heap-pop ( heap -- value key )
 GENERIC: heap-delete ( entry heap -- )
 GENERIC: heap-empty? ( heap -- ? )
 GENERIC: heap-size ( heap -- n )

: up ( n -- m )
    { fixnum } declare 1 fixnum-fast 2/ ; inline

: data-nth ( n heap -- entry )
    data>> nth-unsafe { entry } declare ; inline

: data-first ( heap -- entry )
    data>> first ; inline

: data-set-nth ( entry n heap -- )
    [ [ >>index ] keep ] dip data>> set-nth-unsafe ; inline

: data-push ( entry heap -- n )
    [ heap-size [ >>index ] keep ]
    [ data>> [ set-nth ] 2keep drop ] bi ; inline

GENERIC: heap-compare ( entry1 entry2 heap -- ? )


<PRIVATE

:: sift-up ( heap n -- )
    heap data>>     :> data
    data length     :> end
    n data data-nth :> tmp

    n dup left [ dup end < ] [
        dup 1 fixnum+fast
        dup end < [
            2dup [ data data-nth ] bi@ heap heap-compare
        ] [ f ] if
        [ nip ] [ drop ] if
        [ data data-nth swap data data-set-nth ]
        [ dup left ] bi
    ] while drop

    tmp over data data-set-nth
    heap n rot sift-down ; inline

PRIVATE>
