Idea
Recently, I was doing a project needing a heap structure, i.e. use it to store fringe nodes in Dijstra. The difference between it and a typical heap is that I may need to delete inside elements in this heap. So I made one instead of using PriorityQueue. The idea is to assign every element an ID. The heap class consists of a position array and a data array. Position array records the position of a given ID in the data array.
I initially tried to use generic type directly for the implementation. But I didn’t figure out how to get the id of a generic-type element. Finally, I decided to create a HeapNode class as the element type in heap and use wrapper for different real data type.
Interface
package heap;
public interface Heap<T> {
void insert(T node);
T poll();
void delete(T node);
T peek();
boolean isEmpty();
}
HeapNode
package heap;
public class HeapNode<T> {
public int id;
public int val;
public T data;
public HeapNode(int id, int val, T data) {
this.id = id;
this.val = val;
this.data = data;
}
}
Implementation
package heap;
import java.util.Arrays;
public class MyHeapImpl {
private int lastIndex;
private int[] posArray;
private HeapNode[] dataArray;
public MyHeapImpl(int size) {
lastIndex = 0;
posArray = new int[size];
Arrays.fill(posArray, -1);
dataArray = new HeapNode[size];
}
public boolean isEmpty() {
return lastIndex == 0;
}
public HeapNode peek() {
if (isEmpty()) {
return null;
}
return dataArray[0];
}
public HeapNode poll() {
if (isEmpty()) {
return null;
}
HeapNode ans = peek();
delete(ans);
return ans;
}
public void insert(HeapNode node) {
dataArray[lastIndex] = node;
posArray[node.id] = lastIndex;
swimUp(lastIndex);
lastIndex++;
}
public boolean delete(HeapNode node) {
int pos = posArray[node.id];
if (pos < 0) {
return false;
}
// fix corner case, the one to delete is the last one
if (pos == lastIndex - 1) {
posArray[node.id] = -1;
dataArray[pos] = null;
lastIndex--;
return true;
}
dataArray[pos] = dataArray[lastIndex - 1];
posArray[dataArray[pos].id] = pos;
dataArray[lastIndex - 1] = null;
lastIndex--;
if (pos != 0 && dataArray[pos].val > dataArray[(pos-1) / 2].val) {
swimUp(pos);
} else {
sinkDown(pos);
}
return true;
}
private void swimUp(int pos) {
if (pos == 0 || dataArray[pos].val <= dataArray[(pos-1) / 2].val) {
return;
}
swap(pos, (pos-1) / 2);
swimUp((pos-1) / 2);
}
private void sinkDown(int pos) {
int maxChildPos;
if (2 * pos + 1 >= lastIndex) {
return;
}
if (2 * pos + 2 >= lastIndex) {
maxChildPos = 2 * pos + 1;
} else {
maxChildPos = (dataArray[2 * pos + 1].val > dataArray[2 * pos + 2].val) ?
2 * pos + 1 : 2 * pos + 2;
}
if (dataArray[maxChildPos].val <= dataArray[pos].val) {
return;
}
swap(pos, maxChildPos);
sinkDown(maxChildPos);
}
// need to update pos
private void swap(int pos1, int pos2) {
HeapNode tmp = dataArray[pos1];
dataArray[pos1] = dataArray[pos2];
posArray[dataArray[pos1].id] = pos1;
dataArray[pos2] = tmp;
posArray[dataArray[pos2].id] = pos2;
}
public static void main(String[] args) {
MyHeapImpl test = new MyHeapImpl(100);
for (int i = 0; i < 5; i++) {
test.insert(new HeapNode<Integer>(i,i+1,i+1));
}
test.insert(new HeapNode<Integer>(5,9,9));
System.out.println(test.poll().val);
System.out.println(test.poll().val);
test.insert(new HeapNode<Integer>(5,9,9));
System.out.println(test.poll().val);
while (!test.isEmpty()) {
System.out.println(test.poll().val);
}
}
}
An example of wrapper class
In this case, we can see I wrapped a class GraphNode to HeapNode, thus the heap works for it.
package heap;
import graph.GraphNode;
public class GraphNodeHeap implements Heap<GraphNode>{
private MyHeapImpl myHeap;
public GraphNodeHeap(int size) {
this.myHeap = new MyHeapImpl(size);
}
@Override
public void insert(GraphNode node) {
HeapNode<GraphNode> heapNode = new HeapNode<>(node.getId(), node.getBandwidth(), node);
myHeap.insert(heapNode);
}
@Override
public void delete(GraphNode node) {
HeapNode<GraphNode> heapNode = new HeapNode<>(node.getId(), node.getBandwidth(), node);
myHeap.delete(heapNode);
}
@Override
public boolean isEmpty() {
return myHeap.isEmpty();
}
@Override
public GraphNode poll() {
HeapNode heapNode = myHeap.poll();
return (GraphNode) heapNode.data;
}
@Override
public GraphNode peek() {
HeapNode heapNode = myHeap.peek();
return (GraphNode) heapNode.data;
}
public static void main(String[] args) {
Heap<GraphNode> test = new GraphNodeHeap(5);
GraphNode node = new GraphNode(0);
node.setBandwidth(1);
test.insert(node);
System.out.println(test.poll().getId());
}
}
GraphNode class
package graph;
import java.util.HashSet;
import java.util.Set;
public class GraphNode {
private final int id;
private Set<Edge> edges;
private GraphNode prev;
private Status status;
private int bandwidth;
public GraphNode(int id) {
this.id = id;
this.edges = new HashSet<>();
this.status = Status.UNSEEN;
}
public int getId() {
return this.id;
}
public boolean addEdge(int edgeId, GraphNode n, int weight) {
return this.edges.add(new Edge(edgeId, this, n, weight));
}
public Set<Edge> getNeighbors() {
return this.edges;
}
public GraphNode getPrev() {
return prev;
}
public void setPrev(GraphNode prev) {
this.prev = prev;
}
public Status getStatus() {
return status;
}
public void setStatus(Status status) {
this.status = status;
}
public void setBandwidth(int bandwidth) {
this.bandwidth = bandwidth;
}
public int getBandwidth() {
return this.bandwidth;
}
}
