heap memory in java code example
Example 1: heap in java
In Java PriorityQueue can be used as a Heap.
Min Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
Max Heap:
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
Example 2: heaps in java
public class BinaryHeap {
private static final int d= 2;
private int[] heap;
private int heapSize;
public BinaryHeap(int capacity){
heapSize = 0;
heap = new int[ capacity+1];
Arrays.fill(heap, -1);
}
public boolean isEmpty(){
return heapSize==0;
}
public boolean isFull(){
return heapSize == heap.length;
}
private int parent(int i){
return (i-1)/d;
}
private int kthChild(int i,int k){
return d*i +k;
}
public void insert(int x){
if(isFull())
throw new NoSuchElementException("Heap is full, No space to insert new element");
heap[heapSize++] = x;
heapifyUp(heapSize-1);
}
public int delete(int x){
if(isEmpty())
throw new NoSuchElementException("Heap is empty, No element to delete");
int key = heap[x];
heap[x] = heap[heapSize -1];
heapSize--;
heapifyDown(x);
return key;
}
private void heapifyUp(int i) {
int temp = heap[i];
while(i>0 && temp > heap[parent(i)]){
heap[i] = heap[parent(i)];
i = parent(i);
}
heap[i] = temp;
}
private void heapifyDown(int i){
int child;
int temp = heap[i];
while(kthChild(i, 1) < heapSize){
child = maxChild(i);
if(temp < heap[child]){ heap[i] = heap[child]; }else break; i = child; } heap[i] = temp; } private int maxChild(int i) { int leftChild = kthChild(i, 1); int rightChild = kthChild(i, 2); return heap[leftChild]>heap[rightChild]?leftChild:rightChild;
}
public void printHeap()
{
System.out.print("nHeap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] +" ");
System.out.println();
}
public int findMax(){
if(isEmpty())
throw new NoSuchElementException("Heap is empty.");
return heap[0];
}
public static void main(String[] args){
BinaryHeap maxHeap = new BinaryHeap(10);
maxHeap.insert(10);
maxHeap.insert(4);
maxHeap.insert(9);
maxHeap.insert(1);
maxHeap.insert(7);
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.printHeap();
maxHeap.delete(5);
maxHeap.printHeap();
}
}
Example 3: heap and stack memory in java
Whenever an object is created, it’s always stored in the Heap space, and stack
memory contains the reference to it. Stack memory only contains local
primitive variables and reference variables to objects in heap space.
Objects stored in the heap are globally accessible whereas stack memory can’t
be accessed by other threads.
Memory management in stack is done in LIFO manner whereas it’s more complex in
Heap memory because it’s used globally.
Stack memory is short-lived whereas heap memory lives from the start till the
end of application execution.
Heap memory is used by all the parts of the application, stack memory is used
only by one thread of execution.
When stack memory is full, Java runtime throws
java.lang.StackOverFlowError When heap memory is full, it throws
java.lang.OutOfMemoryError: Java Heap Space error.
Stack memory is faster than heap memory.