JIYIK CN >

A min heap is a heap in which every internal node is less than or equal to the value of its child nodes. We will see in the following points how to implement a min heap with and without using a library.

Minimal heap implementation in Java without using libraries

In this example, we see the implementation without using any library. Here, we have created a class JavaMinHeapin which we have created three instance variables HeapArraywhich is an intarray of type which will hold all the values ​​of the heap, sizeis the size of the heap, maxSizestores HeapArraythe maximum size of . We have also created a variable intof type and initialized it to 1.staticFRONT

maxSizeWe take as a parameter in the constructor and store it maxSizein the instance variable . We initialize with 0 sizeand an array maxSize + 1of size with . We store the minimum value of at the first index of .intHeapArrayIntegerHeapArray

Now we create methods to perform operations on the heap. parent()The function takes positionas a parameter and returns the parent of the node at the position passed. Then we create leftChild(), which returns the left child of the position received as a parameter. The same is true for the right child of the node rightChild()using .(2 * position) + 1

isLeaf()Checks if a node is a leaf node, which means it has any child nodes. swapNodes()is a method that swaps fposthe value of the node at position with the value of at position spos. In the method, we create a tempvariable and initialize it HeapArraywith the position of fposand store the value HeapArrayof sposinto HeapArray[fpos]. Now we tempstore the value of HeapArray[spos]in .

convertToMinHeap()We use isLeafto check if the position received as a parameter is a leaf, if not, we check HeapArrayif the current value of the position is greater than the left or right child. We then check if the left child is less than the right child, if so, we use swapNodes()to swap the nodes and positionpass positionand the left child at . We again use convertToMinHeap()to convert the received left child node into a min-heap.

We insert()insert the value into the min-heap using . In insert(), if the array reaches maxSize, we return without inserting; if not, we ++sizetake the position at and insert the received element HeapArray[++size]. We put 尺寸into 当前. If 当前the element at position is smaller than its parent, we create a cycle and swap the nodes.

To print a min heap, we create printheap()and loop through it HeapArray, where the parent is at ithposition , the left child is at 2 * iposition , and the right child is at 2 * i + 1position . In main()the function, we insert()insert an element in the heap using .

public class JavaMinHeap {
  private final int[] HeapArray;
  private int size;
  private final int maxsize;

  private static final int FRONT = 1;

  public JavaMinHeap(int maxsize) {
    this.maxsize = maxsize;
    this.size = 0;
    HeapArray = new int[this.maxsize + 1];
    HeapArray[0] = Integer.MIN_VALUE;
  }

  private int parent(int position) {
    return position / 2;
  }

  private int leftChild(int position) {
    return (2 * position);
  }

  private int rightChild(int position) {
    return (2 * position) + 1;
  }

  private boolean isLeaf(int position) {
    if (position >= (size / 2) && position <= size) {
      return true;
    }
    return false;
  }

  private void swapNodes(int fpos, int spos) {
    int temp;
    temp = HeapArray[fpos];
    HeapArray[fpos] = HeapArray[spos];
    HeapArray[spos] = temp;
  }

  private void convertToMinHeap(int position) {
    if (!isLeaf(position)) {
      if (HeapArray[position] > HeapArray[leftChild(position)]
          || HeapArray[position] > HeapArray[rightChild(position)]) {
        if (HeapArray[leftChild(position)] < HeapArray[rightChild(position)]) {
          swapNodes(position, leftChild(position));
          convertToMinHeap(leftChild(position));
        } else {
          swapNodes(position, rightChild(position));
          convertToMinHeap(rightChild(position));
        }
      }
    }
  }

  public void insert(int element) {
    if (size >= maxsize) {
      return;
    }
    HeapArray[++size] = element;
    int current = size;

    while (HeapArray[current] < HeapArray[parent(current)]) {
      swapNodes(current, parent(current));
      current = parent(current);
    }
  }

  public void printHeap() {
    for (int i = 1; i <= size / 2; i++) {
      System.out.println("PARENT : " + HeapArray[i]);

      System.out.println("--LEFT CHILD : " + HeapArray[2 * i]);

      System.out.println("--RIGHT CHILD : " + HeapArray[2 * i + 1]);
      System.out.println();
    }
  }

  public static void main(String[] arg) {
    System.out.println("The Min Heap is ");
    JavaMinHeap minHeap = new JavaMinHeap(10);
    minHeap.insert(10);
    minHeap.insert(2);
    minHeap.insert(7);
    minHeap.insert(15);
    minHeap.insert(90);
    minHeap.insert(19);
    minHeap.insert(8);
    minHeap.insert(22);
    minHeap.insert(9);

    minHeap.printHeap();
  }
}

Output:

The Min Heap is 
PARENT : 2
--LEFT CHILD : 9
--RIGHT CHILD : 7

PARENT : 9
--LEFT CHILD : 10
--RIGHT CHILD : 90

PARENT : 7
--LEFT CHILD : 19
--RIGHT CHILD : 8

PARENT : 10
--LEFT CHILD : 22
--RIGHT CHILD : 15

PriorityQueueImplementing a minimum heap in Java

In this program, we use the for creating maximum and minimum heap PriorityQueue. PriorityQueueMultiple methods are provided like add()Insert an element into a queue, peek()Get the head of the queue and remove it, poll()Also retrieve the head of the queue but don't remove it. contains()Checks if the element specified by it is in the queue. remove()Removes the specified element.

We combine PriorityQueueall the functionality of to create and perform min-heap operations. First, we new PriorityQueue()create an empty object Integerof type using . Then we use the method to add our elements. To print and remove the head of the queue, we call to print 10 . We then use the enhanced to print all the elements of the queue. Now we call to print and remove 10. We then remove an element from the queue. We use the returned by to check if the element is in the queue. Finally, to print the remaining values, we convert the queue into an array using .priorityQueueadd()priorityQueue.peek()forpoll()booleancontains()toArray()

import java.util.*;

public class JavaMinHeap {
  public static void main(String[] args) {
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

    priorityQueue.add(10);
    priorityQueue.add(15);
    priorityQueue.add(25);
    priorityQueue.add(200);

    System.out.println("The head value using peek(): " + priorityQueue.peek());

    System.out.println("The queue elements: ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    priorityQueue.poll();
    System.out.println("After removing the head element using poll(): ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    priorityQueue.remove(25);
    System.out.println("After removing 25 with remove(): ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    boolean b = priorityQueue.contains(15);
    System.out.println("Check if priorityQueue contains 15 using contains():  " + b);

    Object[] arr = priorityQueue.toArray();
    System.out.println("Values in array: ");
    for (Object o : arr) System.out.println("Value: " + o.toString());
  }
}

Output:

The head value using peek(): 10
The queue elements: 
10
15
25
200
After removing the head element using poll(): 
15
200
25
After removing 25 with remove(): 
15
200
Check if priorityQueue contains 15 using contains():  true
Values in array: 
Value: 15
Value: 200