% % heapsort by Owen Densmore at Sun Microsystems, Inc. % /SiftDown { % L U => - /U exch def /L exch def /Xl X L get def { L 2 mul 1 add % C (i.e child index) dup U gt {pop exit} if X 1 index get % C Xc 1 index 1 add % C Xc C+1 dup U le { X 1 index get % C Xc C+1 Xc+1 dup 3 index Bigger? {4 2 roll} if pop pop % C' Xc' (largest child) } {pop} ifelse Xl 1 index Bigger? {pop pop exit} if X L 3 -1 roll put /L exch def } loop X L Xl put } def /heapsort { % array proc => array (sorted) 10 dict begin /Bigger? exch cvx def % a b bigger? => t if a>b /X exch def % Make the heap X dup length 1 sub % X N dup 1 sub 2 div floor -1 0 { % X N for: |N/2| -1 0 1 index SiftDown } for % X N % Sort the heap -1 1 { % X i:N -1 1 2 copy 1 index 0 % X i X i X 0 4 copy get 3 1 roll get exch % X i X i X 0 Xi X0 4 1 roll put put % X i 0 exch 1 sub SiftDown } for end } def