heap

Vocabulary

heaps.private

Definition

USING: vectors ;

IN: heaps.private

TUPLE: heap { data vector initial: V{ } } ;

Methods

USING: accessors heaps heaps.private kernel sequences ;

M:: heap heap-delete ( entry heap -- )
    entry heap entry>index
    :> n heap data>> :> data data pop :> nth-entry f entry
    index<< n data length = [
        nth-entry n data data-set-nth n 0 =
        [ t ] [ nth-entry n up data data-nth heap heap-compare ]
        if [ heap n sift-up ] [ heap 0 n sift-down ] if
    ] unless ;


USING: accessors heaps heaps.private sequences ;

M: heap heap-empty? data>> empty? ; inline


USING: accessors heaps heaps.private sequences ;

M: heap heap-peek data>> first >entry< ;


USING: accessors heaps heaps.private kernel sequences ;

M: heap heap-pop*
    dup data>> f over first index<< [ pop ] keep
    [ 2drop ] [ set-first 0 sift-up ] if-empty ;


USING: accessors heaps heaps.private kernel ;

M: heap heap-push*
    [ <entry> dup ] [ data>> data-push ] [ 0 rot sift-down ] tri
    ;


USING: accessors heaps heaps.private sequences ;

M: heap heap-size data>> length ; inline