Paste: Heapify

Author: yuuki
Mode: factor
Date: Mon, 22 Jun 2009 14:56:32
Plain Text |
: (greater) ( keyl l keyi i -- keyl/keyi l/i )
    [ pick over after=? ] dip swap
    [ 2drop ] [ [ 2drop ] 2dip ] if ;

: greater ( key l i heap -- key l/i )
    2dup length < [
        dupd nth swap (greater)
    ] [ 2drop ] if ;

: greatest ( key i heap -- key l/r/p )
    [ over left swap greater ] 2keep [ right ] dip greater ;

: exchange-keys ( keyi i keyl l heap -- keyi l heap )
    [ rot swapd ] dip [ set-nth ] keep ;

: (heapify) ( key i heap -- )
    [ ] [ greatest ] [ drop nip dupd = ] 3tri [ 2drop set-nth ]
    [ rot exchange-keys (heapify) ] if ;

: heapify ( i heap -- )
    [ nth ] 2keep (heapify) ;

New Annotation

Summary:
Author:
Mode:
Body: