Object-Oriented Data-Structures - A Concise and Practical Introduction to Programming Algorithms in Java - page 175

reading its keys from the root to the leaves, level by level. This is a serialization
operation. For the heap of Figure 8.2, we get the following sequence: 37, 22, 31,
16, 17, 2, 23, 12, 6, 9. This sequence implicitly encodes the perfect binary tree.
But this does not mean that any array of integers is a heap in disguise. Indeed,
remember that the heap property of child/parent keys should be satisfied. For
arrays, this core property translates as:

i
2 ⇒

≤ i, j ≤ n, j =

array[ j ]

≥

array[ i ] . 1 (8.1)

Thus the data-structure for representing a heap embedded in an array is as
follows:

public class Heap
int size ;
int [] label ;

static final int MAX SIZE=10000;

Heap ()
this .size=0;
this . label = new i n t [MAX SIZE ] ;
}

Let us now see the various operations acting on the heap compactly encoded
into the array int [] label;

8.3.1 Retrieving the maximal element

As noticed earlier, the maximal key of a heap is necessarily stored at its root.
That is, the maximal priority is encoded in the first cell of the array. Therefore,
the following static function returns the maximal element of a heap given as
argument:

Program 8.3 Retrieving the maximal priority
static int maxHeap( Heap h )
{ return h. label [0]; }

8.3.2 Adding an element

To add an element to the heap, we just need to add it to the first array position
not yet assigned: The first free location of the array corresponds to adding a