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());
Posted by: Guest
on August-31-2020
1
heaps in java
publicclassBinaryHeap {
privatestatic final int d=2;
privateint[] heap;
privateint heapSize;
/**
* This will initialize our heap with default size.
*/publicBinaryHeap(int capacity){
heapSize =0;
heap =newint[ capacity+1];
Arrays.fill(heap, -1);
}
/**
* This will check if the heap is empty or not
* Complexity: O(1)
*/publicbooleanisEmpty(){
return heapSize==0;
}
/**
* This will check if the heap is full or not
* Complexity: O(1)
*/publicbooleanisFull(){
return heapSize == heap.length;
}
privateintparent(int i){
return (i-1)/d;
}
privateintkthChild(int i,int k){
return d*i +k;
}
/**
* This will insert new element in to heap
* Complexity: O(log N)
* As worst case scenario, we need to traverse till the root
*/publicvoidinsert(int x){
if(isFull())
thrownewNoSuchElementException("Heap is full, No space to insert new element");
heap[heapSize++] = x;
heapifyUp(heapSize-1);
}
/**
* This will delete element at index x
* Complexity: O(log N)
*
*/publicintdelete(int x){
if(isEmpty())
thrownewNoSuchElementException("Heap is empty, No element to delete");
int key = heap[x];
heap[x] = heap[heapSize -1];
heapSize--;
heapifyDown(x);
return key;
}
/**
* This method used to maintain the heap property while inserting an element.
*
*/privatevoidheapifyUp(int i) {
int temp = heap[i];
while(i>0&& temp > heap[parent(i)]){
heap[i] = heap[parent(i)];
i =parent(i);
}
heap[i] = temp;
}
/**
* This method used to maintain the heap property while deleting an element.
*
*/privatevoidheapifyDown(int i){
int child;
int temp = heap[i];
while(kthChild(i, 1) < heapSize){
child =maxChild(i);
if(temp < heap[child]){ heap[i] = heap[child]; }elsebreak; i = child; } heap[i] = temp; } privateintmaxChild(int i) { int leftChild =kthChild(i, 1); int rightChild =kthChild(i, 2); return heap[leftChild]>heap[rightChild]?leftChild:rightChild;
}
/**
* This method used to print all element of the heap
*
*/publicvoidprintHeap()
{
System.out.print("nHeap = ");
for (int i =0; i < heapSize; i++)
System.out.print(heap[i] +" ");
System.out.println();
}
/**
* This method returns the max element of the heap.
* complexity: O(1)
*/publicintfindMax(){
if(isEmpty())
thrownewNoSuchElementException("Heap is empty.");
return heap[0];
}
publicstaticvoidmain(String[] args){
BinaryHeap maxHeap =newBinaryHeap(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();
}
}
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.
Forgot your account's password or having trouble logging into your Account? Don't worry, we'll help you to get back your account. Enter your email address and we'll send you a recovery link to reset your password. If you are experiencing problems
resetting your password contact us
Check Your Email and Click on the link sent to your email