# Heap Sort

The first routine creates a heap ...

```* HEAP.BUILD builds a heap to take further data from.
************************************************************************

SUBROUTINE HEAP.BUILD( DATA, MAT DATARRAY, ITEMCOUNT, DELIM, SORT)
* Arguments:
*  DATA - a delimited dynamic array of data to sort
*  DATARRAY - supplied by the caller - a dimensioned array large enough to hold all the data
*  ITEMCOUNT - returned - the number of items in the array
*  DELIM - the dynamic array delimiter
*  SORT - the sort type eg AL or DR

* If DELIM is "" then it assumes that the dimensioned array has already
* been set up. Note that the dimensioned array must be correctly sized
* by the caller. It's okay for it to be too big, but many (all?) MV's
* can't resize an array passed as an argument, so if it's too small this
* subroutine can't increase its size.

************************************************************************

IF DELIM NE "" THEN
MATPARSE DATARRAY FROM DATA USING DELIM SETTING ITEMCOUNT
END

* return -1 as an error if there's no data
IF ITEMCOUNT EQ 0 THEN
ITEMCOUNT = -1
RETURN
END

* sort out justification, and whether the sort is ascending or descending
SORTORDER = UPCASE( SORT[1,1] )
JUST = UPCASE( SORT[2,1] )

* for each item, bubble it up into position
FOR II = 2 TO ITEMCOUNT
CURRENTITEM = II
NEXTITEM = INT( CURRENTITEM * 0.5)
LOOP WHILE NEXTITEM
* compare with the item half-way between current and the top of the array
TEST = COMPARE( DATARRAY( NEXTITEM), DATARRAY( CURRENTITEM), JUST)
IF SORTORDER EQ "D" THEN TEST = 0 - TEST ;* reverse order

IF TEST LE 0 THEN
* terminate bubble - this item is in position
NEXTITEM = 0
END ELSE
* swap item and loop to see if it goes higher
TEMP = DATARRAY( NEXTITEM)
DATARRAY( NEXTITEM) = DATARRAY( CURRENTITEM)
DATARRAY( CURRENTITEM) = TEMP
CURRENTITEM = NEXTITEM
NEXTITEM = INT( CURRENTITEM * 0.5)
END
REPEAT
NEXT

RETURN
END
```

The second routine returns items one by one, in sorted order

```* HEAP.GETNEXT removes the next value from a heap
************************************************************************

SUBROUTINE HEAP.GETNEXT( RESULT, MAT DATARRAY, ITEMCOUNT, SORT, DEDUP)
* Arguments:
*  RESULT - the value returned
*  DATARRAY - a heap created by HEAP.BUILD
*  ITEMCOUNT - the number of items in DATARRAY - modified by this routine
*  SORT - the sort type eg AL or DR
*  DEDUP - remove duplicates without returning them?

* The calling routine needs to check ITEMCOUNT - when it gets to zero
* there's nothing left to return. Don't rely on "RESULT EQ ''" because
* the result could validly be null (or anything else, for that matter).

************************************************************************

IF ITEMCOUNT LE 0 THEN RETURN ;* don't do anything

* sort out justification, and whether the sort is ascending or descending
SORTORDER = UPCASE( SORT[1,1] )
JUST = UPCASE( SORT[2,1] )

* save the top entry as the result to be returned
RESULT = DATARRAY( 1)
CURRENTPOS = 1

* bubble the lower values up
LOOP WHILE CURRENTPOS LT ITEMCOUNT
NEXTPOS = CURRENTPOS * 2

IF NEXTPOS GE ITEMCOUNT THEN
* next test position is off the end of the array (or is the last item)
DATARRAY(CURRENTPOS) = DATARRAY(ITEMCOUNT)

IF NEXTPOS NE ITEMCOUNT THEN
* this bit is necessary because we shrink the array every time. It's not
* necessary in a standard heap sort, but because we're moving the bottom
* element to some place at "random" in the array, we need to make sure it
* is correctly placed again in the heap. So just bubble this item up the
* heap like when we built it in the first place.
PREVPOS = INT( CURRENTPOS * 0.5)
LOOP WHILE PREVPOS
TEST = COMPARE( DATARRAY( PREVPOS), DATARRAY( CURRENTPOS), JUST)
IF SORTORDER EQ "D" THEN TEST = 0 - TEST ;* reverse order
IF TEST LE 0 THEN PREVPOS = 0 ELSE
TEMP = DATARRAY( PREVPOS)
DATARRAY( PREVPOS) = DATARRAY( CURRENTPOS)
DATARRAY( CURRENTPOS) = TEMP
END
REPEAT
END

CURRENTPOS = ITEMCOUNT ;* loop will terminate

END ELSE
* Okay, we haven't fallen off the end of the heap - compare next two
* items. Whichever is smallest, move up to replace current entry, then
* loop to replace the item we've just moved up.
TEST = COMPARE( DATARRAY( NEXTPOS), DATARRAY( NEXTPOS+1), JUST)
IF SORTORDER EQ "D" THEN TEST = 0 - TEST ;* reverse order
IF TEST LT 0 THEN
DATARRAY(CURRENTPOS) = DATARRAY(NEXTPOS)
CURRENTPOS = NEXTPOS
END ELSE
DATARRAY(CURRENTPOS) = DATARRAY(NEXTPOS+1)
CURRENTPOS = NEXTPOS+1
END
END

REPEAT
ITEMCOUNT -= 1

IF DEDUP THEN
* if top entry in heap is identical to current result, then call self to
* throw it away. ITEMCOUNT test is needed because the first test will
* always be true on the last entry.
LOOP WHILE RESULT EQ DATARRAY( 1) AND ITEMCOUNT GT 0
CALL *HEAP.GETNEXT( JUNK, MAT DATARRAY, ITEMCOUNT, SORT, 0)
REPEAT
END

RETURN
END
```

These two routines could easily be combined into a proper sort routine.