After reading about heap I tried to implement the heap. Below is my code along with test. Any feedback with respect to correctness, performance is welcome.
import java.util.Arrays;
public class BinaryHeap2 {
private int[] heap;
private int size;
private int capacity;
public BinaryHeap2(){
capacity = 100;
size = 0;
heap = new int[capacity];
}
public BinaryHeap2(int capacity){
this.capacity = capacity;
size = 0;
heap = new int[this.capacity];
}
public void offer(int i){
if(size>=capacity){
capacity = capacity*2;
int[] tmp = new int[capacity];
System.arraycopy(heap, 0, tmp, 0, heap.length);
heap = tmp;
}
heap[size++] = i;
heapifyUp(size-1);
}
private void heapifyUp(int position){
int parent = (position-1)/2;
while(heap[parent]>heap[position]){
swap(parent,position);
position = parent;
parent = (position-1)/2;
}
}
private void swap(int i, int j){
int t = heap[i];
heap[i] = heap[j];
heap[j] = t;
}
public int peek(){
return heap[0];
}
public int poll(){
int min = heap[0];
heap[0] = heap[size-1];
size--;
if(size>1)
heapifyDown(0);
return min;
}
public int getSize(){
return size;
}
private void heapifyDown(int i) {
int leftChild = 2*i+1;
int rightChild = 2*i+2;
int childToSwap = heap[leftChild]<heap[rightChild]?leftChild:rightChild;
while(heap[i]> heap[childToSwap]){
swap(i,childToSwap);
i = childToSwap;
leftChild = 2*i+1;
rightChild = 2*i+2;
if(rightChild>=size||leftChild>=size)break;
childToSwap = heap[leftChild]<heap[rightChild]?leftChild:rightChild;
}
}
public void display(){
System.out.println(Arrays.toString(heap));
}
}
Below is the Unit test
import static org.junit.Assert.assertEquals;
import org.junit.Before;
import org.junit.Test;
public class BinaryHeap2Test {
BinaryHeap2 heap;
@Before
public void setUp(){
heap = new BinaryHeap2(3);
}
@Test
public void test() {
heap.offer(7);
heap.offer(6);
heap.offer(3);
heap.offer(2);
heap.offer(1);
heap.offer(5);
heap.offer(4);
heap.offer(3);
heap.offer(2);
heap.display();
assertEquals(1, heap.peek());
assertEquals(heap.poll(), 1);
assertEquals(heap.poll(), 2);
assertEquals(heap.poll(), 2);
assertEquals(heap.poll(), 3);
assertEquals(heap.poll(), 3);
assertEquals(heap.poll(), 4);
heap.offer(1);
heap.display();
assertEquals(heap.poll(), 1);
assertEquals(heap.poll(), 5);
assertEquals(heap.poll(), 6);
assertEquals(heap.poll(), 7);
heap.display();
}
@Test
public void test2(){
heap.offer(300);
heap.offer(200);
heap.offer(100);
assertEquals(100, heap.poll());
heap.display();
assertEquals(200, heap.poll());
heap.display();
assertEquals(300, heap.poll());
heap.display();
heap.offer(2);
assertEquals(2, heap.peek());
heap.offer(100);
heap.offer(1);
heap.offer(5);
assertEquals(1, heap.poll());
assertEquals(2, heap.poll());
assertEquals(5, heap.poll());
assertEquals(100, heap.poll());
}
}
rightChild = leftChild + 1
. \$\endgroup\$