Min Heap and Max Heap Implementation in Java
Implement a heap data structure in Java.
Prerequisite:
In the above post, we have introduced the heap data structure and covered heapify-up, push, heapify-down, and pop operations. In this post, Java implementation of Max Heap and Min Heap is discussed.
1. Max Heap implementation in Java
Following is Java implementation of max-heap data structure. We have tried to keep the implementation similar to the java.util.PriorityQueue class.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 |
import java.util.Arrays; import java.util.Vector; // A class for implementing the priority queue class PriorityQueue { // vector to store heap elements private Vector<Integer> A; // constructor: use the default initial capacity of a vector public PriorityQueue() { A = new Vector(); } // constructor: set a custom initial capacity for vector public PriorityQueue(int capacity) { A = new Vector(capacity); } // return parent of `A[i]` private int parent(int i) { // if `i` is already a root node if (i == 0) { return 0; } return (i - 1) / 2; } // return left child of `A[i]` private int LEFT(int i) { return (2*i + 1); } // return right child of `A[i]` private int RIGHT(int i) { return (2*i + 2); } // swap values at two indexes void swap(int x, int y) { // swap with a child having greater value Integer temp = A.get(x); A.setElementAt(A.get(y), x); A.setElementAt(temp, y); } // Recursive heapify-down procedure. Here, the node at index `i` // and its two direct children violate the heap property private void heapify_down(int i) { // get left and right child of node at index `i` int left = LEFT(i); int right = RIGHT(i); int largest = i; // compare `A[i]` with its left and right child // and find the largest value if (left < size() && A.get(left) > A.get(i)) { largest = left; } if (right < size() && A.get(right) > A.get(largest)) { largest = right; } if (largest != i) { // swap with a child having greater value swap(i, largest); // call heapify-down on the child heapify_down(largest); } } // Recursive heapify-up procedure private void heapify_up(int i) { // check if the node at index `i` and its parent violates // the heap property if (i > 0 && A.get(parent(i)) < A.get(i)) { // swap the two if heap property is violated swap(i, parent(i)); // call heapify-up on the parent heapify_up(parent(i)); } } // return size of the heap public int size() { return A.size(); } // check if the heap is empty or not public Boolean isEmpty() { return A.isEmpty(); } // insert a specified key into the heap public void add(Integer key) { // insert a new element at the end of the vector A.addElement(key); // get element index and call heapify-up procedure int index = size() - 1; heapify_up(index); } // Function to remove and return an element with the highest priority // (present at the root). It returns null if the queue is empty public Integer poll() { try { // if the heap is empty, throw an exception if (size() == 0) { throw new Exception("Index is out of range (Heap underflow)"); } // element with the highest priority int root = A.firstElement(); // or A.get(0); // replace the root of the heap with the last element of the vector A.setElementAt(A.lastElement(), 0); A.remove(size() - 1); // call heapify-down on the root node heapify_down(0); // return root element return root; } // catch and print the exception catch (Exception ex) { System.out.println(ex); return null; } } // Function to return an element with the highest priority // (present at the root). It returns null if the queue is empty public Integer peek() { try { // if the heap has no elements, throw an exception if (size() == 0) { throw new Exception("Index out of range (Heap underflow)"); } // otherwise, return the top (first) element return A.firstElement(); // or A.get(0); } // catch the exception and print it, and return null catch (Exception ex) { System.out.println(ex); return null; } } // Function to remove all elements from the priority queue public void clear() { System.out.print("Emptying queue: "); while (!A.isEmpty()) { System.out.print(poll() + " "); } System.out.println(); } // Returns true if the queue contains the specified element public Boolean contains(Integer i) { return A.contains(i); } // Returns an array containing all elements in the queue public Integer[] toArray() { return A.toArray(new Integer[size()]); } } class Main { public static void main (String[] args) { // create a priority queue with an initial capacity of 10. // The value of an element decides the priority of it. PriorityQueue pq = new PriorityQueue(10); // insert three integers pq.add(3); pq.add(2); pq.add(15); // print priority queue size System.out.println("Priority queue size is " + pq.size()); // search 2 in priority queue Integer searchKey = 2; if (pq.contains(searchKey)) { System.out.println("Priority queue contains " + searchKey + "\n"); } // empty queue pq.clear(); if (pq.isEmpty()) { System.out.println("The queue is empty"); } System.out.println("\nCalling remove operation on an empty heap"); System.out.println("The element with the highest priority is " + pq.poll()); System.out.println("\nCalling peek operation on an empty heap"); System.out.println("The element with the highest priority is " + pq.peek() + System.lineSeparator()); // again insert three integers pq.add(5); pq.add(4); pq.add(45); // construct an array containing all elements present in the queue Integer[] I = pq.toArray(); System.out.println("Printing array: " + Arrays.toString(I)); System.out.println("\nThe element with the highest priority is " + pq.poll()); System.out.println("The element with the highest priority is " + pq.peek()); } } |
Output:
Priority queue size is 3
Priority queue contains 2
Emptying queue: 15 3 2
The queue is empty
Calling remove operation on an empty heap
java.lang.Exception: Index out of range(Heap underflow)
The element with the highest priority is null
Calling peek operation on an empty heap
java.lang.Exception: Index out of range (Heap underflow)
The element with the highest priority is null
Printing array: [45, 4, 5]
The element with the highest priority is 45
The element with the highest priority is 5
Priority queue size is 3
Priority queue contains 2
Emptying queue: 15 3 2
The queue is empty
Calling remove operation on an empty heap
java.lang.Exception: Index out of range(Heap underflow)
The element with the highest priority is null
Calling peek operation on an empty heap
java.lang.Exception: Index out of range (Heap underflow)
The element with the highest priority is null
Printing array: [45, 4, 5]
The element with the highest priority is 45
The element with the highest priority is 5
2. Min Heap implementation in Java
The min-heap implementation is very similar to the max-heap implementation discussed above. The highlighted portion in the following code marks its differences with max-heap implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 |
import java.util.Arrays; import java.util.Vector; // A class for implementing the Priority queue class PriorityQueue { // vector to store heap elements private Vector<Integer> A; // constructor: use the default initial capacity of a vector public PriorityQueue() { A = new Vector(); } // constructor: set a custom initial capacity for vector public PriorityQueue(int capacity) { A = new Vector(capacity); } // return parent of `A[i]` private int parent(int i) { // if `i` is already a root node if (i == 0) { return 0; } return (i - 1) / 2; } // return left child of `A[i]` private int LEFT(int i) { return (2*i + 1); } // return right child of `A[i]` private int RIGHT(int i) { return (2*i + 2); } // swap values at two indexes void swap(int x, int y) { // swap with a child having greater value Integer temp = A.get(x); A.setElementAt(A.get(y), x); A.setElementAt(temp, y); } // Recursive heapify-down procedure. Here, the node at index `i` // and its two direct children violate the heap property private void heapify_down(int i) { // get left and right child of node at index `i` int left = LEFT(i); int right = RIGHT(i); int smallest = i; // compare `A[i]` with its left and right child // and find the smallest value if (left < size() && A.get(left) < A.get(i)) { smallest = left; } if (right < size() && A.get(right) < A.get(smallest)) { smallest = right; } if (smallest != i) { // swap with a child having lesser value swap(i, smallest); // call heapify-down on the child heapify_down(smallest); } } // Recursive heapify-up procedure private void heapify_up(int i) { // check if the node at index `i` and its parent violates // the heap property if (i > 0 && A.get(parent(i)) > A.get(i)) { // swap the two if heap property is violated swap(i, parent(i)); // call heapify-up on the parent heapify_up(parent(i)); } } // return size of the heap public int size() { return A.size(); } // check if the heap is empty or not public Boolean isEmpty() { return A.isEmpty(); } // insert a specified key into the heap public void add(Integer key) { // insert a new element at the end of the vector A.addElement(key); // get its index and call the heapify-up procedure int index = size() - 1; heapify_up(index); } // Function to remove and return an element with the highest priority // (present at the root). It returns null if the queue is empty public Integer poll() { try { // if the heap is empty, throw an exception if (size() == 0) { throw new Exception("Index is out of range (Heap underflow)"); } // element with the highest priority int root = A.firstElement(); // or A.get(0); // replace the root of the heap with the last element of the vector A.setElementAt(A.lastElement(), 0); A.remove(size() - 1); // call heapify-down on the root node heapify_down(0); // return root element return root; } // catch and print the exception catch (Exception ex) { System.out.println(ex); return null; } } // Function to return an element with the highest priority // (present at the root). It returns null if the queue is empty public Integer peek() { try { // if the heap has no elements, throw an exception if (size() == 0) { throw new Exception("Index out of range (Heap underflow)"); } // otherwise, return the top (first) element return A.firstElement(); // or A.get(0); } // catch the exception and print it, and return null catch (Exception ex) { System.out.println(ex); return null; } } // Function to remove all elements from the priority queue public void clear() { System.out.print("Emptying queue: "); while (!A.isEmpty()) { System.out.print(poll() + " "); } System.out.println(); } // Returns true if the queue contains the specified element public Boolean contains(Integer i) { return A.contains(i); } // Returns an array containing all elements in the queue public Integer[] toArray() { return A.toArray(new Integer[size()]); } } class Main { public static void main (String[] args) { // create a priority queue with an initial capacity of 10. // The value of an element decides the priority of it. PriorityQueue pq = new PriorityQueue(10); // insert three integers pq.add(3); pq.add(2); pq.add(15); // print priority queue size System.out.println("Priority queue size is " + pq.size()); // search 2 in priority queue Integer searchKey = 2; if (pq.contains(searchKey)) { System.out.println("Priority queue contains " + searchKey + "\n"); } // empty queue pq.clear(); if (pq.isEmpty()) { System.out.println("The queue is empty"); } System.out.println("\nCalling remove operation on an empty heap"); System.out.println("The element with the highest priority is " + pq.poll()); System.out.println("\nCalling peek operation on an empty heap"); System.out.println("The element with the highest priority is " + pq.peek() + System.lineSeparator()); // again insert three integers pq.add(5); pq.add(4); pq.add(45); // construct an array containing all elements present in the queue Integer[] I = pq.toArray(); System.out.println("Printing array: " + Arrays.toString(I)); System.out.println("\nThe element with the highest priority is " + pq.poll()); System.out.println("The element with the highest priority is " + pq.peek()); } } |
Output:
Priority queue size is 3
Priority queue contains 2
Emptying queue: 2 3 15
The queue is empty
Calling remove operation on an empty heap
java.lang.Exception: Index out of range(Heap underflow)
The element with the highest priority is null
Calling peek operation on an empty heap
java.lang.Exception: Index out of range (Heap underflow)
The element with the highest priority is null
Printing array: [4, 5, 45]
The element with the highest priority is 4
The element with the highest priority is 5
Priority queue size is 3
Priority queue contains 2
Emptying queue: 2 3 15
The queue is empty
Calling remove operation on an empty heap
java.lang.Exception: Index out of range(Heap underflow)
The element with the highest priority is null
Calling peek operation on an empty heap
java.lang.Exception: Index out of range (Heap underflow)
The element with the highest priority is null
Printing array: [4, 5, 45]
The element with the highest priority is 4
The element with the highest priority is 5
Following is the time complexity of implemented heap operations:
add()andpoll()takes O(log(n)) time.toArray()andcontains()takes O(n) time.peek()andsize()andisEmpty()takes O(1) time.
Also See:
Exercise: Implement Heap in Java using ArrayList instead of a Vector.
References: https://en.wikipedia.org/wiki/Heap_(data_structure)
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)