import java.util.ArrayList; import java.util.Comparator; public class BinaryHeap { protected ArrayList heap; protected Comparator compareFunction = null; public BinaryHeap (Comparator compare Function) { this.compareFunction = compareFunction; } protected int getLeft (int index) { } return 2* (index)+1; protected int getRight (int index) { return 2* (index)+2; } protected int getParent (int index) { } return index>0? (index+1)/2 -1 -1; public void build Heap (ArrayList list) { heap = list; for (int i=(heap.size())/2-1; i >= 0; i--) { heapify(i); } } public int size() { } return heap.size(); public T pop() { if (heap.size() > 0) { } T top heap.get(0); heap.set(0, heap.getLast()); heap.removeLast(); heapify(0); return top; else { return null; } private void heapify(int index) { int L= getLeft (index); int R = getRight (index); int optimal = index; if (Lheap.size() && compareFunction.compare(heap.get(L), heap.get(index)) > 0) { } optimal = L; if (Rheap.size() && compareFunction.compare (heap.get(R), heap.get(optimal)) > 0) { optimal = R; } if (optimal != index) { T tmp heap.get(index); heap.set(index, heap.get(optimal)); heap.set(optimal, tmp); heapify(optimal); } } public void display() { if (heap null) { return; } int current Level = 0; for (int i = 0; i < heap.size(); i++) { int level = (int) (Math. log(i+1)/Math.log(2)); int maxLevels = (int) (Math.log(heap.size())/Math.log(2)); String spacing = ""; for (int j = 0; j < Math.pow(2, maxLevels-level); j++) { spacing += ""; } if (current Level

Related questions

Question

Part A - Heapsort

We have included code in Java for a Binary Heap implementation.The first task is to use the heap to sort three separate arrays. The sorted arrays do not have to be ”in place”

Use the implementation of the Binary Heap to:
(a) Sort a list of floats from high to low.
(b) Sort a list of strings alphabetically.
(c) Sort integers by their second digit only (low to high).

Here is the rest of code:

import java.util.ArrayList;

public class TestHeap {

public static void main(String[] args) {

ArrayList<Integer> list = new ArrayList<Integer>();

list.add(8);

list.add(5);

list.add(12);

list.add(15);

list.add(20);

list.add(8);

list.add(5);

list.add(18);

list.add(5);

BinaryHeap<Integer> heap = new BinaryHeap<Integer>(new MaxIntegerComparorator());

heap.buildHeap(list);

heap.display();

}

import java.util.Comparator;

public class MaxIntegerComparorator implements Comparator<Integer> {

@Override

public int compare(Integer o1, Integer o2) {

return o1.compareTo(o2);

}

import java.util.Comparator;

public class MinIntegerComparorator implements Comparator<Integer> {

@Override

public int compare(Integer o1, Integer o2) {

return o1.compareTo(o2) * -1;

}

import java.util.ArrayList;
import java.util.Comparator;
public class BinaryHeap<T> {
protected ArrayList<T> heap;
protected Comparator<T> compareFunction = null;
public BinaryHeap (Comparator<T> compare Function) {
this.compareFunction = compareFunction;
}
protected int getLeft (int index) {
}
return 2* (index)+1;
protected int getRight (int index) {
return 2* (index)+2;
}
protected int getParent (int index) {
}
return index>0? (index+1)/2 -1 -1;
public void build Heap (ArrayList<T> list) {
heap = list;
for (int i=(heap.size())/2-1; i >= 0; i--) {
heapify(i);
}
}
public int size() {
}
return heap.size();
public T pop() {
if (heap.size() > 0) {
}
T top heap.get(0);
heap.set(0, heap.getLast());
heap.removeLast();
heapify(0);
return top;
else {
return null;
}
private void heapify(int index) {
int L= getLeft (index);
int R = getRight (index);
int optimal = index;
if (Lheap.size() && compareFunction.compare(heap.get(L),
heap.get(index)) > 0) {
}
optimal = L;
if (Rheap.size() && compareFunction.compare (heap.get(R),
heap.get(optimal)) > 0) {
optimal = R;

}
if (optimal != index) {
T tmp heap.get(index);
heap.set(index, heap.get(optimal));
heap.set(optimal, tmp);
heapify(optimal);
}
}
public void display() {
if (heap null) {
return;
}
int current Level = 0;
for (int i = 0; i < heap.size(); i++) {
int level = (int) (Math. log(i+1)/Math.log(2));
int maxLevels = (int) (Math.log(heap.size())/Math.log(2));
String spacing = "";
for (int j = 0; j < Math.pow(2, maxLevels-level); j++) {
spacing += "";
}
if (current Level <level) {
System.out.println();
current Level = level;
}
}
System.out.print(spacing + heap.get(i));
System.out.println();

Expert Solution

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here