Question
I need hep to write a java program to implement priority queue using a heap. You have to store the heap in arrays. For example, one array called "priority" contains the priorities of the nodes; and another array called "data" contains the data of the nodes.
To have FIFO behavior for elements with equal priority, you have to use a third array called "entered". The value of entered[i] tells when the data in node number i entered the priority queue. Make sure to keep track of how many elements are in the heap so that, if the size of the heap reaches the size of the arrays, you can increase the size of the arrays.
Requirements of the implementation: 3 arrays (priority, data, entered)
Please also provide a testing "main" method.
Explanation / Answer
import java.util.*; public abstract class Heap { private List heap; public Heap() { heap = new ArrayList(); } public void push(Object obj) { heap.add(obj); pushUp(heap.size()-1); } public Object pop() { if (heap.size() > 0) { swap(0, heap.size()-1); Object result = heap.remove(heap.size()-1); pushDown(0); return result; } else { return null; } } public Object getFirst() { return heap.get(0); } public Object get(int index) { return heap.get(index); } public int size() { return heap.size(); } protected abstract boolean isGreaterOrEqual(int first, int last); protected int parent(int i) { return (i - 1) / 2; } protected int left(int i) { return 2 * i + 1; } protected int right(int i) { return 2 * i + 2; } protected void swap(int i, int j) { Object tmp = heap.get(i); heap.set(i, heap.get(j)); heap.set(j, tmp); } public void pushDown(int i) { int left = left(i); int right = right(i); int largest = i; if (left 0) { System.out.println(h.pop()); } } }