Priority Queue with MinHeap and Adjacency List Graphs in Java
Priority Queue with MinHeap in Java
Note: This is a minimum priority queue (MinHeap).
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.NoSuchElementException;
public class EDPriorityQueue<E> {
private static final int DEFAULT_INITIAL_CAPACITY = 11;
E[] data;
int size;
private Comparator<E> comparator;
//CONSTRUCTORS
public EDPriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public EDPriorityQueue(Comparator<E> comp) {
this(DEFAULT_INITIAL_CAPACITY, comp);
}
public EDPriorityQueue(int capacity, Comparator<E> comp) {
if (capacity < 1)
throw new IllegalArgumentException();
this.data = (E[]) new Object[capacity];
this.comparator = comp;
}
public EDPriorityQueue(Collection<E> c) {
this(c.size() + 1, null);
size = c.size();
int i = 0;
for (E elem : c) {
data[i] = elem;
i++;
}
heapify();
}
public EDPriorityQueue(Collection<E> c, Comparator<E> comp) {
this(c.size(), comp);
size = c.size();
int i = 0;
for (E elem : c) {
data[i] = elem;
i++;
}
heapify();
}
//PRIVATE METHODS
/**
* Compares two objects and returns a negative number if object left is less than
* object right, zero if are equal, and a positive number if object left is
* greater than object right
*/
int compare(E left, E right) {
if (comparator != null) { //A comparator is defined
return comparator.compare(left, right);
} else {
return (((Comparable<E>) left).compareTo(right));
}
}
private void swap(int i, int j) {
E elem_i = this.data[i];
this.data[i] = data[j];
this.data[j] = elem_i;
}
//Sinks element at pos parent as low as possible
private void sink(int parent) {
int leftChild = 2 * parent + 1;
int min = parent;
if (leftChild < size)
if (compare(data[leftChild], data[parent]) < 0)
min = leftChild;
int rightChild = leftChild + 1;
if (rightChild < size) {
if (compare(data[rightChild], data[min]) < 0)
min = rightChild;
}
if (min != parent) {
swap(min, parent);
sink(min);
}
}
//Floats element at pos child towards the root
private void floating(int child) {
if (child > 0) {
int parent = (child - 1) / 2;
if (compare(data[parent], data[child]) > 0) {
swap(child, parent);
child = parent;
floating(child);
}
}
}
//Doubles array size
private void grow() {
int initial_capacity = data.length;
E[] old = this.data;
data = (E[]) new Object[initial_capacity * 2];
for (int i = 0; i < size; i++) {
this.data[i] = old[i];
}
}
//Reorders data to have heap order
private void heapify() {
for (int i = (size / 2) - 1; i >= 0; i--) {
sink(i);
}
}
private int indexOf(E item, int current) {
if (compare(item, data[current]) == 0)
return current;
else if (compare(item, data[current]) < 0)
return -1;
else {
int leftChild = 2 * current + 1;
if (leftChild < size) {
int position = indexOf(item, leftChild);
if (position == -1) {
int rightChild = 2 * current + 2;
if (rightChild < size) {
return indexOf(item, rightChild);
}
}
return position;
}
return -1;
}
}
//PUBLIC METHODS
public boolean contains(E item) {
int pos = indexOf(item, 0);
return (pos != -1);
}
public boolean isEmpty() {
return (this.size == 0);
}
public int size() {
return size;
}
public boolean add(E item) {
data[size] = item;
floating(size);
size++;
grow();
return true;
}
/**
* Removes the front of the queue if the priority queue is not empty. If the
* queue is empty, returns NoSuchElementException
*
* @return E smallest element in the queue
*/
public E remove() throws NoSuchElementException {
if (isEmpty())
throw new NoSuchElementException();
E result = data[0]; //the root of the heap
if (size > 1) {
//remove the last item in the array and put it in the root position
data[0] = data[size - 1]; //puts last item in the root position
sink(0);
}
size = size - 1; //deletes last element
return result;
}
//Returns the smallest element of the minHeap or largest if it is a maxHeap
public E element() throws NoSuchElementException {
if (!isEmpty()) {
return data[0];
}
throw new NoSuchElementException();
}
//Removes the first occurrence of item
public boolean remove(E item) {
if (size != 0) {
int position = indexOf(item, 0);
if (position < 0) {
return false;
}
swap(position, size - 1);
size--;
if (position >= size / 2) {
int parent = (position - 1) / 2;
sink(parent);
} else {
sink(position);
}
return true;
}
return false;
}
}
Graphs Using Adjacency List in Java
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.HashSet;
import java.util.Set;
/**
* Note:
*
* @param <T> The base type of the nodes
* @param <W> The base type of the weights of the edges
*/
public class EDListGraph<T, W> implements EDGraph<T, W> {
private class Node<T> {
T data;
List<EDEdge<W>> lEdges;
Node(T data) {
this.data = data;
this.lEdges = new LinkedList<EDEdge<W>>();
}
public boolean equals(Object other) {
if (this == other)
return true;
if (!(other instanceof Node))
return false;
//System.out.println("equals de node");
Node<T> anotherNode = (Node<T>) other;
return data.equals(anotherNode.data);
}
}
// Private data
private ArrayList<Node<T>> nodes;
private int size; //real number of nodes
private boolean directed;
//CONSTRUCTORS
/**
* Note:
*
* @param directed = true for directed edges and false for non directed edges.
*/
public EDListGraph() {
directed = false; //not directed
nodes = new ArrayList<Node<T>>();
size = 0;
}
public EDListGraph(boolean dir) {
directed = dir;
nodes = new ArrayList<Node<T>>();
size = 0;
}
//METHODS
public int getSize() {
return size;
}
public int nodesSize() {
return nodes.size();
}
public boolean isEmpty() {
return size == 0;
}
public int insertNode(T item) {
int i = 0;
while (i < nodes.size() && nodes.get(i).data != null)
i++;
Node<T> newNode = new Node<T>(item);
if (i < nodes.size())
nodes.set(i, newNode);
else
nodes.add(newNode);
size++;
//System.out.println("Inserted in position "+i);
return i;
}
public int getNodeIndex(T item) {
Node<T> aux = new Node<T>(item);
return nodes.indexOf(aux);
}
public T getNodeValue(int index) throws IndexOutOfBoundsException {
return nodes.get(index).data;
}
//Undirected graph
public boolean insertEdge(EDEdge<W> edge) {
int sourceIndex = edge.getSource();
int targetIndex = edge.getTarget();
if (sourceIndex >= 0 && sourceIndex < nodes.size() && targetIndex >= 0 && targetIndex < nodes.size()) {
Node<T> nodeSr = nodes.get(sourceIndex);
Node<T> nodeTa = nodes.get(targetIndex);
if (nodeSr.data != null && nodeTa.data != null) {
if (!nodeSr.lEdges.contains(edge)) {
nodeSr.lEdges.add(edge);
nodes.set(sourceIndex, nodeSr);
if (!directed) { //undirected
EDEdge<W> reverse = new EDEdge<W>(targetIndex, sourceIndex, edge.getWeight());
nodeTa.lEdges.add(reverse);
nodes.set(targetIndex, nodeTa);
}
return true;
} else
System.out.println("The graph already has this edge: " + edge.toString());
}
}
return false;
}
public boolean insertEdge(T fromNode, T toNode, W label) {
int fromIndex = getNodeIndex(fromNode);
if (fromIndex < 0)
fromIndex = this.insertNode(fromNode);
int toIndex = this.getNodeIndex(toNode);
if (toIndex < 0)
toIndex = this.insertNode(toNode);
EDEdge<W> e = new EDEdge<W>(fromIndex, toIndex, label);
this.insertEdge(e);
return true;
}
public EDEdge<W> getEdge(int source, int dest) {
if (source < 0 || source >= nodes.size())
return null;
Node<T> node = nodes.get(source);
if (node.data == null)
return null;
for (EDEdge<W> edge : node.lEdges)
if (edge.getTarget() == dest)
return edge;
return null;
}
public EDEdge<W> removeEdge(int source, int target, W weight) {
if (source < 0 || source >= nodes.size() || target < 0 || target >= nodes.size())
return null;
if (nodes.get(source).data != null && nodes.get(target).data != null) {
EDEdge<W> edge = new EDEdge<W>(source, target, weight);
Node<T> node = nodes.get(source);
int i = node.lEdges.indexOf(edge);
if (i != -1) {
edge = node.lEdges.remove(i);
if (!directed) {
EDEdge<W> reverse = new EDEdge<W>(target, source, weight);
nodes.get(target).lEdges.remove(reverse);
}
return edge;
}
}
return null;
}
public T removeNode(int index) {
if (index >= 0 && index < nodes.size()) {
if (!directed) {
Node<T> node = nodes.get(index);
for (EDEdge<W> edge : node.lEdges) {
int target = edge.getTarget();
W label = edge.getWeight();
EDEdge<W> other = new EDEdge<W>(target, index, label);
nodes.get(target).lEdges.remove(other);
}
} else { //directed
for (int i = 0; i < nodes.size(); i++) {
if (i != index && nodes.get(i).data != null) {
Node<T> node = nodes.get(i);
for (EDEdge<W> edge : node.lEdges) {
if (index == edge.getTarget()) //any weight/label
node.lEdges.remove(edge);
}
}
}
}
Node<T> node = nodes.get(index);
node.lEdges.clear();
T ret = node.data;
node.data = null; //It is not remove, data is set to null
nodes.set(index, node);
size--;
System.out.println("Deleted position: " + index);
return ret;
}
return null;
}
/*
* Returns an array with the shortest distance from an initial node item to the
* rest of the nodes. Breadth-first search algorithm taking into account that
* in the array we have to return the distance that separates each node from
* the initial node. If item does not belong to the graph, it returns null.
*/
public int[] distanceToAll(T item) {
int[] newArray = new int[nodes.size()];
int i;
int pos = getNodeIndex(item);
if (pos < 0)
return null;
else {
for (i = 0; i < newArray.length; i++)
newArray[i] = -1; //All to -1
newArray[pos] = 0; //The same to 0
Queue<Integer> queue = new LinkedList<>();
queue.add(pos); //Add element to the queue
while (!queue.isEmpty()) {
int n = queue.remove();
Node<T> aux = nodes.get(n);
for (EDEdge edge : aux.lEdges) {
int x = edge.getTarget();
if (newArray[x] == -1) {
newArray[x] = newArray[n] + 1;
queue.add(x);
}
}
}
}
return newArray;
}
/*
* Returns the set of common friends between item1 and item2. If any of the
* friends is not included in the graph, it will return null.
*/
public Set<T> common(T item1, T item2) {
int pos = getNodeIndex(item1);
int pos2 = getNodeIndex(item2);
Node<T> node = nodes.get(pos);
Node<T> node2 = nodes.get(pos2);
if (pos == -1 || pos2 == -1)
return null;
else {
Set<T> destination1 = new HashSet<>();
for (EDEdge<W> edge : node.lEdges) {
destination1.add(getNodeValue(edge.getTarget()));
}
Set<T> destination2 = new HashSet<>();
for (EDEdge<W> edge2 : node2.lEdges) {
destination2.add(getNodeValue(edge2.getTarget()));
}
destination1.retainAll(destination2);
return destination1;
}
}
public Set<Integer> getAdyacentNodes(int index) {
if (index < 0 || index >= nodes.size())
return new HashSet<Integer>();
Set<Integer> ret = new HashSet<Integer>();
for (EDEdge<W> ed : nodes.get(index).lEdges) {
ret.add(ed.getTarget());
}
return ret;
}
/*
* Given the names of two people, item1 and item2, returns a set with the
* friends of item2, who are not friends of item1. In the case that any of them
* does not belong to the graph returns null.
*/
public Set<T> suggest(T item1, T item2) {
Set<T> all = new HashSet<>();
int pos = getNodeIndex(item1);
int pos2 = getNodeIndex(item2);
Node<T> node = nodes.get(pos);
Node<T> node2 = nodes.get(pos2);
if (pos == -1 || pos2 == -1)
return null;
else {
Set<T> destination1 = new HashSet<>();
for (EDEdge<W> edge : node.lEdges) {
destination1.add(getNodeValue(edge.getTarget()));
}
Set<T> destination2 = new HashSet<>();
for (EDEdge<W> edge2 : node2.lEdges) {
destination2.add(getNodeValue(edge2.getTarget()));
if (!all.contains(getNodeValue(edge2.getTarget())))
all.add(getNodeValue(edge2.getTarget()));
}
destination1.retainAll(destination2);
all.removeAll(destination1);
return all;
}
}
/*Returns the label of the node with more connections*/
public T mostPopular() {
int max = 0;
T mostPopular = null;
for (int i = 0; i < size; i++) {
Node<T> node = nodes.get(i);
if (node.lEdges.size() > max) {
max = node.lEdges.size();
mostPopular = node.data;
}
}
return mostPopular;
}
public Set<T> getNodes() {
Set<T> s = new HashSet<T>();
for (int i = 0; i < nodes.size(); i++) {
if (nodes.get(i).data != null)
s.add(nodes.get(i).data);
}
return s;
}
}