Question

Java programming

Write the max-heapify code and test it and then write the program to find the three largest values of the array without sorting the entire array to get values.

Answer 1

CODE

public class Main {

private int[] arr;

private int size;

private int maximum;

public Main(int maxsize)

{

this.maximum = maxsize;

this.size = 0;

arr = new int[this.maximum + 1];

arr[0] = Integer.MAX_VALUE;

}

private int parent(int pos)

{

return pos / 2;

}

private int leftChild(int pos)

{

return (2 * pos);

}

private int rightChild(int pos)

{

return (2 * pos) + 1;

}

private boolean isLeaf(int pos)

{

if (pos >= (size / 2) && pos <= size) {

return true;

}

return false;

}

private void swap(int fpos, int spos)

{

int tmp;

tmp = arr[fpos];

arr[fpos] = arr[spos];

arr[spos] = tmp;

}

private void maxHeapify(int pos)

{

if (isLeaf(pos))

return;

if (arr[pos] < arr[leftChild(pos)] ||

arr[pos] < arr[rightChild(pos)]) {

if (arr[leftChild(pos)] > arr[rightChild(pos)]) {

swap(pos, leftChild(pos));

maxHeapify(leftChild(pos));

}

else {

swap(pos, rightChild(pos));

maxHeapify(rightChild(pos));

}

}

}

public void insert(int element)

{

arr[++size] = element;

int current = size;

while (arr[current] > arr[parent(current)]) {

swap(current, parent(current));

current = parent(current);

}

}

public int findMax()

{

int popped = arr[1];

arr[1] = arr[size--];

maxHeapify(1);

return popped;

}

public static void main(String[] arg)

{

int arr[] = {14, 1, -9, 17, 85, 11, 45, 9};

Main maxHeap = new Main(arr.length);

for (int i=0; i<arr.length; i++) {

maxHeap.insert(arr[i]);

}

System.out.println("The largest three values are: ");

System.out.println(maxHeap.findMax());

System.out.println(maxHeap.findMax());

System.out.println(maxHeap.findMax());

}

}