This applet visually demonstrates the use of Replacement Selection in programming. View the applet in the Applet section below. The usage of the applet is described in the following Usage section. For those interested, the Display and design of the applet are also described.
Usage of the applet is broken into two steps. First you must
populate the input file
that records will be read from.
This contains several integer values representing records in the
file. You can either choose to input them one at a time using the
Add button (You will be prompted for the next
Integer to add), or you can select 18 random values usign the
Random button.
Once the values are entered to your liking, you can click the Create Runs button to begin processing the Input file. You can now use the Step and Autostep buttons to step through the lines of Pseudocode that manipulate the heap and runs.
At any time during the population or run creation phases, you can reset the applet to its initial state by using the Reset button.
The display is standard by now. The Input buttons and box are displayed across the top. The Pseudocode is displayed all in one window to below left. The heap and current run are displayed to the below right, the heap above and the run below.
The standard StructuredPanel design will be used. The following
Pseudocode will be used:
heapsize = 4
heap = new int[heapsize]
last = heapsize - 1
done = false
public void createRuns(File file) {
for (int i = 0; i < heapsize; i++)
heap[i] = getNext()
do {
buildHeap()
while (last >= -1) {
next = getNext()
if (heap[0] == -1)
done = true
break
sendOutput(heap[0])
if (next >= heap[0])
heap[0] = next
else
heap[0] = heap[last]
heap[last] = next
last--
siftdown(0)
}
last = heapsize -1
} while (!done)
}
This code works by assuming that the siftdown method will place the -1 (would be null in an object based implementation) values as being greater than any positive integer, so they always sift down to the leaves.