TI-BASIC:Heap

A [*http://en.wikipedia.org/wiki/Heap_(data_structure) heap] heap is a special type of [*http://en.wikipedia.org/wiki/Tree_(data_structure) tree]. A max heap is a binary tree that has the property that every node's children are smaller than itself, and both its left and right subtrees are heaps. A min heap is like a max heap the only difference is that every node's children are greater than itself. A heap, no matter what kind is always complete. This means that a heap can always be represented by a list. For every element at index i in a list its parent is at i/2 and its children are at 2i and 2i+1. This can be seen below:

[-- image]

In TI-Basic as in most other languages the best way to implement a heap is as a list. There are two main operations that we can do. The first is to add to the heap. This adds a number to the end of the list and then inserts it in the right place. The second operation is to remove from the list. This removes and returns the first element of the list and then fixes the rest of the list so that everything is in the correct order.

The add code is as follows:

:1+dim(L₁)→I
:N→L₁(I)
:1→Z
:While I/2≥1
:If L₁(I)>L₁(int(I/2))
:Then
:L₁(I)→T
:L₁(int(I/2))→L₁(I)
:T→L₁(int(I/2))
:int(I/2)→I
:Else
:1→I
:End