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 B - Priority Queue

For this part of the assignment, you are to implement a priority queue using the Binary Heap. You will need to create the following:
• insert(...)
• maximum()
• increase key(...)
Feel free to name these functions as you see fit. You are also welcome to create
any other methods that may be helpful in your implementation. Keep in mind,
one way to extend the heap is through inheritance (if useful).

Use the implementation of the priority queue to:
(a) Add items to the list.
(b) Pop off a few items, but not the whole list. The items that were extracted
should be sorted by highest priority.
(c) Add a few items that are low priority.
(d) Add a few items that are high priority.
(e) Pop items off the list and you should see the high priority items show up
before the low priority items.

Here is code below in addition to the BinaryHeap.java (attached):

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