Wow, this is pretty cool. With just this description, I developed my first correctly working heapsort! And the rest of the related algorithms come easily (at least how I worked them in my mind) and they are super fast.
edit: Super fast in a computational efficiency way, not in a TI-BASIC implementation way :P
Inputs: L1=(almost) heap, K=offset, N=number of elements of the heap
This code essentially assumes that starting at leaf K, it's sub-trees are all heaps. This joins those sub-trees with K at the head, then it properly reorganizes so that the entire thing is once again a heap.
This code allows us to recursively build a heap from the bottom up, while doing it efficiently.
K→C Ans2→B While B≤N If B<N Then If L1(B)<L1(B+1 B+1→B End If L1(B)>L1(C Then L1(B→A L1(C→L1(B A→L1(C End B→C B2→B End
This code take input as Ans and L1. The first 'Ans' elements of L1 are converted into a heap structure.
Ans→N If Ans<2 Return 1 While Ans2≤N Ans2 End Ans-1→D For K,D,1,-1 prgmHEAPJOIN End
This takes L1 as a list, and Ans as the number of elements to sort. This then sorts from least to greatest.
prgmHEAPIFY N→M For(I,0,M-1 L1(M-I→A L1(1→L1(M-I A→L1(1 1→K N-1→N prgmHEAPJOIN End
This heapsort routine isn't very useful for TI-BASIC, but it's fun for demonstration :)
47%? Take a look and try to imagine how cool 100% will be. This has won zContest 2011 and made news on TICalc. This compromise between Assembly and BASIC parses like BASIC and is fast like assembly. Grammer 2