1
2In Java PriorityQueue can be used as a Heap.
3
4Min Heap
5PriorityQueue<Integer> minHeap = new PriorityQueue<>();
6
7
8Max Heap:
9PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
1Whenever an object is created, it’s always stored in the Heap space, and stack
2memory contains the reference to it. Stack memory only contains local
3primitive variables and reference variables to objects in heap space.
4Objects stored in the heap are globally accessible whereas stack memory can’t
5be accessed by other threads.
6Memory management in stack is done in LIFO manner whereas it’s more complex in
7Heap memory because it’s used globally.
8Stack memory is short-lived whereas heap memory lives from the start till the
9end of application execution.
10Heap memory is used by all the parts of the application, stack memory is used
11only by one thread of execution.
12When stack memory is full, Java runtime throws
13java.lang.StackOverFlowError When heap memory is full, it throws
14java.lang.OutOfMemoryError: Java Heap Space error.
15Stack memory is faster than heap memory.
16
1public class BinaryHeap {
2
3 private static final int d= 2;
4 private int[] heap;
5 private int heapSize;
6
7 /**
8 * This will initialize our heap with default size.
9 */
10 public BinaryHeap(int capacity){
11 heapSize = 0;
12 heap = new int[ capacity+1];
13 Arrays.fill(heap, -1);
14
15 }
16
17 /**
18 * This will check if the heap is empty or not
19 * Complexity: O(1)
20 */
21 public boolean isEmpty(){
22 return heapSize==0;
23 }
24
25 /**
26 * This will check if the heap is full or not
27 * Complexity: O(1)
28 */
29 public boolean isFull(){
30 return heapSize == heap.length;
31 }
32
33
34 private int parent(int i){
35 return (i-1)/d;
36 }
37
38 private int kthChild(int i,int k){
39 return d*i +k;
40 }
41
42 /**
43 * This will insert new element in to heap
44 * Complexity: O(log N)
45 * As worst case scenario, we need to traverse till the root
46 */
47 public void insert(int x){
48 if(isFull())
49 throw new NoSuchElementException("Heap is full, No space to insert new element");
50 heap[heapSize++] = x;
51 heapifyUp(heapSize-1);
52 }
53
54 /**
55 * This will delete element at index x
56 * Complexity: O(log N)
57 *
58 */
59 public int delete(int x){
60 if(isEmpty())
61 throw new NoSuchElementException("Heap is empty, No element to delete");
62 int key = heap[x];
63 heap[x] = heap[heapSize -1];
64 heapSize--;
65 heapifyDown(x);
66 return key;
67 }
68
69 /**
70 * This method used to maintain the heap property while inserting an element.
71 *
72 */
73 private void heapifyUp(int i) {
74 int temp = heap[i];
75 while(i>0 && temp > heap[parent(i)]){
76 heap[i] = heap[parent(i)];
77 i = parent(i);
78 }
79 heap[i] = temp;
80 }
81
82 /**
83 * This method used to maintain the heap property while deleting an element.
84 *
85 */
86 private void heapifyDown(int i){
87 int child;
88 int temp = heap[i];
89 while(kthChild(i, 1) < heapSize){
90 child = maxChild(i);
91 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;
92 }
93
94 /**
95 * This method used to print all element of the heap
96 *
97 */
98 public void printHeap()
99 {
100 System.out.print("nHeap = ");
101 for (int i = 0; i < heapSize; i++)
102 System.out.print(heap[i] +" ");
103 System.out.println();
104 }
105 /**
106 * This method returns the max element of the heap.
107 * complexity: O(1)
108 */
109 public int findMax(){
110 if(isEmpty())
111 throw new NoSuchElementException("Heap is empty.");
112 return heap[0];
113 }
114
115 public static void main(String[] args){
116 BinaryHeap maxHeap = new BinaryHeap(10);
117 maxHeap.insert(10);
118 maxHeap.insert(4);
119 maxHeap.insert(9);
120 maxHeap.insert(1);
121 maxHeap.insert(7);
122 maxHeap.insert(5);
123 maxHeap.insert(3);
124
125 maxHeap.printHeap();
126 maxHeap.delete(5);
127 maxHeap.printHeap();
128
129 }
130}
131
1Whenever an object is created, it’s always stored in the Heap space, and stack
2memory contains the reference to it. Stack memory only contains local
3primitive variables and reference variables to objects in heap space.
4Objects stored in the heap are globally accessible whereas stack memory can’t
5be accessed by other threads.
6Memory management in stack is done in LIFO manner whereas it’s more complex in
7Heap memory because it’s used globally.
8Stack memory is short-lived whereas heap memory lives from the start till the
9end of application execution.
10Heap memory is used by all the parts of the application, stack memory is used
11only by one thread of execution.
12When stack memory is full, Java runtime throws
13java.lang.StackOverFlowError When heap memory is full, it throws
14java.lang.OutOfMemoryError: Java Heap Space error.
15Stack memory is faster than heap memory.