Array-based binary min-heap implementation package data_structures; import java.
ID: 3545861 • Letter: A
Question
Array-based binary min-heap implementation
package data_structures;
import java.util.Iterator;
public class BinaryHeapPriorityQueue<E> implements PriorityQueue<E> {
public boolean insert(E object) {
}
public E remove() {
}
public E peek() {
}
public int size() {
}
public boolean contains(E object) {
}
public Iterator<E> iterator() {
}
public void clear() {
}
public boolean isEmpty() {
}
public boolean isFull() {
}
}
/* The PriorityQueue ADT may store objects in any order. However,
removal of objects from the PQ must follow specific criteria.
The object of highest priority that has been in the PQ longest
must be the object returned by the remove() method. FIFO return
order must be preserved for objects of identical priority.
Ranking of objects by priority is determined by the Comparable<E>
interface. All objects inserted into the PQ must implement this
interface. Priorities may be of any type that supports comparison;
a lower priority value indicates a higher priority. i.e. given two
objects a and b, if a < b then a has higher priority than b.
*/
package data_structures;
import java.util.Iterator;
public interface PriorityQueue<E> extends Iterable<E> {
public static final int DEFAULT_MAX_CAPACITY = 1000;
// Inserts a new object into the priority queue. Returns true if
// the insertion is successful. If the PQ is full, the insertion
// is aborted, and the method returns false.
public boolean insert(E object);
// Removes the object of highest priority that has been in the
// PQ the longest, and returns it. Returns null if the PQ is empty.
public E remove();
// Returns the object of highest priority that has been in the
// PQ the longest, but does NOT remove it.
// Returns null if the PQ is empty.
public E peek();
// Returns the number of objects currently in the PQ.
public int size();
// Returns true if the element is in the priority queue, and
// false if it is not (or the pq is empty).
public boolean contains(E object);
// Returns an iterator of the objects in the PQ, in no particular
// order. The iterator must be fail-fast.
public Iterator<E> iterator();
// Returns the PQ to an empty state.
public void clear();
// Returns true if the PQ is empty, otherwise false
public boolean isEmpty();
// Returns true if the PQ is full, otherwise false.
public boolean isFull();
}
Explanation / Answer
package data_structures;
import java.util.Iterator;
public class BinaryHeapPriorityQueue<E> implements PriorityQueue<E> {
private E[] data;
private int size;
public BinaryHeapPriorityQueue() {
data = (E[])new Object[DEFAULT_MAX_CAPACITY];
size = 0;
}
public boolean insert(E object) {
if (isFull())
return false;
data[size] = object;
size++;
int current = size - 1;
int parent = (current - 1) / 2;
while (parent >= 0)
{
Comparable<E> comp = (Comparable<E>)data[current];
if (comp.compareTo(data[parent]) >= 0)
break;
E temp = data[parent];
data[parent] = data[current];
data[current] = temp;
current = parent;
parent = (current - 1) / 2;
}
return true;
}
public E remove() {
if (size == 0)
return null;
E rootData = data[0];
int current = size - 1;
data[0] = data[current];
size--;
current = 0;
boolean done = false;
while (current < size && !done)
{
int left = current * 2 + 1;
int right = current * 2 + 2;
if (left < size)
{
int min = left;
if (right < size)
{
Comparable<E> comp = (Comparable<E>)data[min];
if (comp.compareTo(data[right]) > 0)
min = right;
}
Comparable<E> comp = (Comparable<E>)data[current];
if (comp.compareTo(data[min]) > 0)
{
E temp = data[min];
data[min] = data[current];
data[current] = temp;
current = min;
} else
done = true;
}
else
done = true;
}
return rootData;
}
public E peek() {
if (size == 0)
return null;
return data[0];
}
public int size() {
return size;
}
public boolean contains(E object) {
for (int i = 0; i < size; i++)
if (object.equals(data[i]))
return true;
return false;
}
public Iterator<E> iterator() {
return new Iterator<E>() {
private int index = 0;
public boolean hasNext() {
return index < size;
}
public E next() {
E tmp = data[index];
index++;
return tmp;
}
public void remove() {
}
};
}
public void clear() {
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == data.length;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.