Heap implementation in JavaIn Java, Heap is a special type of data structure where the root node or parent node is compared with its left and right children and arranged according to the order. Suppose, x is a root node and y is the child node, property key(x)<= key(y) will generate minheap, and that relation is referred to as "Heap Property". Based on the order of the parent and child nodes, Heap can be classified in two forms, i.e., Min heap and Max heap. Let's understand both of them one by one and implement the code in Java. Min heapMin heap is a special type of heap data structure that is a complete binary tree in itself . Min heap has the following properties:
We can perform the following three operations in Min heap: insertNode()We can perform insertion in the Min heap by adding a new key at the end of the tree. If the value of the inserted key is smaller than its parent node, we have to traverse the key upwards for fulfilling the heap property. The insertion process takes O(log n) time. extractMin()It is one of the most important operations which we perform to remove the minimum value node, i.e., the root node of the heap. After removing the root node, we have to make sure that heap property should be maintained. The extractMin() operation takes O(Logn) time to remove the minimum element from the heap. getMin()The getMin() operation is used to get the root node of the heap, i.e., minimum element in O(1) time. Example: Min heap Algorithm MinHeapJavaImplementation.java Output: Max heapMax heap is another special type of heap data structure that is also a complete binary tree in itself in Java. Max heap has the following properties:
We can perform the following three operations in Max heap: insertNode()We can perform insertion in the Max heap by adding a new key at the end of the tree. If the value of the inserted key is greater than its parent node, we have to traverse the key upwards for fulfilling the heap property. The insertion process takes O(log n) time. extractMax()It is one of the most important operations which we perform to remove the maximum value node, i.e., the root node of the heap. After removing the root node, we have to make sure that heap property should be maintained. The extractMax() operation takes O(Log n) time to remove the maximum element from the heap. getMax()The getMax() operation is used to get the root node of the heap, i.e., maximum element in O(1) time. Example: Min heap Algorithm MaxHeapJavaImplementation.java Output:
Next TopicHow to Check null in Java
