/* Heap sort -- increasing order */

#include "harp1.h"

const dw = 9;
const aw = 8;
const ae = (1 << aw);

const max = ae - 1;
const half_max = max div 2;

const zero = 0 : 1;
const one  = 1 : 1;

#define left(x)  (zero @ ((x) <- (aw - 1)))
#define right(x) (one  @ ((x) <- (aw - 1)))
 
void main(chan(in)  STDIN           : dw,
          chan(out) STDOUT          : dw,
          eram heap[ae] = harp1lram : dw)
{
    int x, y, z;
    int i, n, swsc_i, swsc_j; 
    bool did_swap;

    void swap_with_smaller_child() {

	x, did_swap = heap[swsc_i], 0;
	swsc_j, y = left(swsc_i), heap[left(swsc_i)];

	/* Is the left child a valid position in the heap? */
	if ((left(swsc_i) @ zero) <= (n @ zero)) {

	    /* Is the right child a valid position in the heap? */
	    if ((right(swsc_i) @ zero) <= (n @ zero)) {

		/* If so, is it the smaller child? */
		z = heap[right(swsc_i)];
		if (z < y)
		    swsc_j, y = right(swsc_i), heap[right(swsc_i)];

	    }

	    /* y contains the value of smaller child, swsc_j its position */

	    if (y < x) {                /* Is child smaller than parent?  */
		heap[swsc_i] = y;       /* Yes, swap */
		par {
		    heap[swsc_j] = x;
		    did_swap = 1;
		}
	    }

	}
    }

    void bubble_down() {
	do {
	    swap_with_smaller_child();  /* Bubble down one place if possible */
	    swsc_i = swsc_j;            /* New position to bubble from       */
                                        /* If swapped, and we are not on     */
                                        /* the bottom row, continue bubbling */
	} while (did_swap & ~(swsc_i \\ (aw - 1)));
    }

    void build_heap() {
	i, n = half_max, max;        /* For each parent in the heap... */
	do {                       
	    swsc_i, i = i, i - 1;    /* Bubble the value down if possible */
	    bubble_down();
	} while (i != 0);            /* Backwards. */
    }
    
    void input_data() {
	n = 0;
	do {
	    n = n + 1;
	    STDIN ? heap[n];
	} while (n != max);
    }

    void output_sorted() {
	i = max;
	do {
	    STDOUT ! heap[1];                /* Output minimum value       */
	    y = heap[i];                     /* Pick last value off heap   */
	                                     /* Place value at top of heap */
	    heap[1], n, swsc_i, i = y, i - 1, 1, i - 1;   
	    bubble_down();                   /* Restore heap ordering      */
	} while (i != 0);
    }


    /* Main program */

    input_data();
    build_heap();
    output_sorted();

}