Home » Heap implementation in Java

Heap implementation in Java

by Online Tutorials Library

Heap implementation in Java

In 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 min-heap, 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 heap

Min heap is a special type of heap data structure that is a complete binary tree in itself . Min heap has the following properties:

  1. Root node value is always smaller in comparison to the other nodes of the heap.
  2. Each internal node has a key value that is always smaller or equal to its children.

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:

Heap implementation in Java

Min heap Algorithm

MinHeapJavaImplementation.java

Output:

Heap implementation in Java

Max heap

Max 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:

  1. Root node value is always greater in comparison to the other nodes of the heap.
  2. Each internal node has a key value that is always greater or equal to its children.

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:

Heap implementation in Java

Min heap Algorithm

MaxHeapJavaImplementation.java

Output:

Heap implementation in Java


You may also like