Question

(java)

Create a specification(your choice) of a data abstraction , decide a rep for the data abstraction. Write the abstraction function and the rep invariant for the rep.

Note* add comments for explanation..

Answer 1

Rep invariant is some sort of protection on state(s) against operations that have the capacity to`modify`. Therfore, Heap sort on array is great example to show the rep invarirant. where array is used to store elements in such a manner when converted to binary tree parent is max/min than both children.

thus, abstract function would be heapify function where each parent node’s key >= children’s keys.

Its given below -

//sort applied on array (can be abstracted)
public void sort(int arr[])
{
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

for (int i=n-1; i>=0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

heapify(arr, i, 0);
}
}

//rep invariancy condition
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;

if (l < n && arr[l] > arr[largest])
largest = l;

if (r < n && arr[r] > arr[largest])
largest = r;

if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

heapify(arr, n, largest);
}
}