1. Modelling the heap concept
The initial model of a 7 element heap is constructed by executing
include("stage2.s");
include("stage2.d");
include("stage2.e");
This creates an environment (Model 2) in which the user can set the first
and last element of the heap, by redefining first and last.
e.g. first = 3; last = 6;
Nodes that represent heap elements are indicated by circles.
Edges that are associated with meaningful comparisons in the heap
structure are represented by lines in the tree visualisation.
A red line indicates that (the value of) a child is greater than
(that of) its parent, and a blue line that it is less than its parent.
(A black line is used to indicate that a child is equal to its parent.)
The circle surrounding a node is depicted in blue if the heap
condition prevails at that node, and is otherwise red.
The user can perform experiments to illustrate the heap concept by
changing the first and last elements of the heap, and assigning
different values to the nodes. To change the value at a node use
a redefinition of the form:
val[3] = 34;
To change the value of the entire array, redefine the variable val
as a list of 7 integers. (The type of data that can be attached
to nodes is not restricted to integer values, but the visualisation
is not presently suitable for real numbers or larger integers.
The radius of the circles around nodes is fixed at 20 pixels,
and the adapted line definition, which overwrites the definition
of a standard donald line - such as appears after the inclusion of
the file stage2.d in the input phase - reduces the length of lines
by lopping 10% of each end. The visualisation could cope with
larger integers if these parameters had values that were dependent
on the size of the integer value at the node. See the definitions
of radius, _l12 - the eden image of the donald line l12, and
the functions newline and shortline.)
The interval between first and last forms a heap if and only if
there are no red edges in the visualisation.
It is instructive to observe how the heap condition at a node
(hc1 for node1 etc) and the index of the child with greater value
attached (ixgtch1 for node1 etc) is affected by resetting first
and last.
As a preliminary to understanding the concept of a heap on a general
interval, it is helpful to experiment with a heap on the complete
binary tree with 7 nodes. For this purpose, simpler definitions
of the heap condition and of the index of the child with greater
value suffice. The modified definitions can be introduced via
include("change21");
In the model created in this way (Model 1), the definition of the
essential observables is easier to understand, as the user doesn't
need to consider whether or not nodes of the tree are in the heap.
By way of comparison typical definitions of the heap condition and of
the index of the child with greater value in the two models are:
hc1 is (ord12 >= 0) && (ord13 >= 0);
hc1 is (!inhp1)
|| (inhp1 && (!inhp2 || (inhp2 && (ord12 == 1)) && (!inhp3 || (ord13 == 1))));
ixgtch1 is (val[2]>val[3]) ? 2: 3;
ixgtch1 is (!inhp3) ? 2: ((val[2]>val[3]) ? 2: 3);
It is instructive to express these definitions in words, and explain their
significance. Notice the default by which a node not in the heap is
deemed to satisfy the heap condition. This is a useful convention when
processing the tree / heap in an exploratory fashion, but may be redundant
once suitable constraints are placed upon the nodes that are accessed for
processing (e.g. in automatic execution of heapsort). This illustrates
a general principle that operates in the construction of definitive scripts,
whereby definitions that are initially simple get to be refined to more
complex forms as the model becomes richer, but can subsequently be
simplified when the execution of the model is more circumscribed.
2. Simulation of the heapsort process
Perhaps the simplest concept in using a heap for sorting is that heap
construction serves to identify the largest element. (It is easy to
modify the visualisation in models 1 and 2 so that the largest
element in the array has a surrounding circle that is distinguished
in some way. It is then clear that the heap condition is always
satisfied at the node that holds the greatest value, and that when
the entire tree is a heap the greatest value will be attached to
the root. (In general, 'a maximal value' is more precise than 'the greatest'.)
A small script to effect this modification that can be included into models 1
and 2 is supplied by maxelt.e.)
The principal action needed to construct a heap involves changing the
value at a node that violates the heap condition. This is achieved by
exchanging the value at the node for the greater of the two values that
appear at the children of the node. The procedure used for this is
a simple exchange of indices, as listed in exc.e.
The procedure exc() can be used as the basis for agent action both
automatically and under user control. The eden actions to represent
such agents can take one of two forms.
For automatic execution (corresponding to posting an agent at a node
to restore the heap condition as and when it is violated), an appropriate
eden action is specified as follows:
proc maintainheap1: hc1
{
if (!hc1) exc(1, ixgtch1);
}
To introduce user control, it is necessary to attach an observable to the
agent that is under user control. The heap restoration process is then
invoked only when the user requests it.
proc maintainheap1 : hc1, update1 {
if (!hc1 && update1) {
exc(1, ixgtch1);
update1 = 0;
}
}
To enable the user to set the update flags using the mouse, an action
associated with selection of a node in the tree is required:
near = 10;
func abs {
para x;
return (x>=0)?x: -x;
};
proc selectp1: _p1, heapwin_mouse
{
if (abs((heapwin_mouse[4]-_p1[2])+(heapwin_mouse[5]-_p1[3])) < near)
update1 = (heapwin_mouse[2]==4)?1:0;
};
In this context, near determines how near to the node the user has to
click for selection.
A simple model to demonstrate how agents at each node that establish the
heapsort condition can maintain a heap on 7 elements can be derived from
model 1 by introducing the files exc.e and change13.1. After any redefinition
of values in the array val, a heap is immediately constructed by invocation
of the maintainheap actions. A more sophisticated variant of this model
carries out the heap construction automatically, but in a step-by-step
manner, awaiting a mouse click in window that holds the tree diagram:
proc maintainheap1: hc1, next
{
if (!hc1 && next==1) {
todo("exc(1, ixgtch1);");
next =0;
}
}
proc nextstep : heapwin_mouse {
if (heapwin_mouse[2]==4 && next==0) next++;
}
The set-up for this model is via change13.2. Note that the way in which
agents act in this model is non-deterministic and sequential, but always
leads to the construction of a valid heap.
To carry out the same process in a more user-directed manner, the file
change23 can be introduced (this redefines the maintainheap agent at each
node so that it is activated only when the user selects that node
and so sets the appropriate update flag). Including the file change23
in Model 1 creates an environment in which the user can explore strategies
for constructing a heap on 7 elements. Including the same file in Model 2
creates an environment in which the user can simulate the entire heapsort
procedure. This involves manipulation of first and last in conjunction with
heap construction.
3. Automating the heapsort process
Animation of the heapsort method can be achieved by combining change13.2
(which allows step-by-step execution of heap maintenance), with the following
script:
first = 4;
last = 7;
next=0;
/* the above definitions initialise the heap */
proc heapmake : next
{
if (next && first>1) {
first--; next=0;
}
}
/* the above procedure describes the step-by-step heap construction */
proc outsort : next
{
if (first==1 && last>0 && next) {
last--;
exc(1,last+1);
next=0;
}
}
/* the above procedure describes the step-by-step output of the sorted array */
This only works as it stands because the order of actions is coincidentally
right.
Refinements to the definitions of outsort and heapmake needed to make
things work more generally have been introduced in animate.e and add.e.
There are several ways in which the model can be run: here is one that
visits a range of different functionalities:
tkeden stage2.s stage2.d stage2.e
... this sets up a heap model where first and last can be changed.
include("change21");
... simplifies the model to 7-elements, so that heap conditions are simpler etc
include("change12");
... restores the original model of the heap
include("change23");
... this sets up the context for user execution of heapsort.
include("change13.2");
include("animate.e");
include("add.e");
... this gives an environment for automatic execution of heapsort, each step
in response to a user click in the window containing the tree.
(next = 0 is a precondition for the model to work in automatic mode.)