Min Heap in Java

A min heap is a type of data structure that is used in a variety of applications such as priority queues, heapsort, and more. It is a complete binary tree that follows the heap property, which states that the value of any node is greater than or equal to the value of its parent node. In this article, we will discuss the features of a min heap, and how it works. We will also discuss the time and space complexities for insertion, deletion, access and search, and provide several Java code examples to illustrate each operation. Lastly, we will provide several coding exercises with solutions to test the reader’s understanding of min heaps.

What is a Min Heap?

A min heap is a type of binary tree. It is a complete binary tree, meaning that all levels of the tree are filled except for possibly the last level, which is filled from left to right. The heap property states that the value of any node is greater than or equal to the value of its parent node. In a min heap, this means that the root node has the smallest value in the tree.

The main operations with a min heap are insertion, deletion, and search. Insertion adds a new item to the heap, while deletion removes an item from the heap. Search finds an item in the heap. All of these operations can be performed in time proportional to the height of the tree, which is log n, where n is the number of items in the tree.

Time Complexity

When using a min heap, the time complexity for insertion, deletion, access, and search will all depend on the height of the tree, which is log n, where n is the number of items in the tree. The time complexity for insertion and deletion is O(log n), while the time complexity for access and search is O(1).

Space Complexity

The space complexity for a min heap is O(n), where n is the number of items in the tree. This is because each node in the tree requires a certain amount of space to store its data.

Java Code Examples

Now that we have discussed the features of a min heap and the time and space complexities for the operations, let’s look at some Java code examples to illustrate each operation.

Insertion

To insert an item into a min heap, we first need to find the appropriate location for the item. This can be done by comparing the value of the item with the value of its parent node. If the value of the item is smaller than the value of its parent node, then we can insert the item into the heap.

public void insert(int item) {
  // Get the size of the heap
  int n = heap.size();
  
  // Add the item to the end of the heap
  heap.add(item);
  
  // Compare the item to its parent node
  int i = n;
  int parent = (i-1)/2;
  
  // If the item is smaller than its parent, swap them
  while (i > 0 && heap.get(i) < heap.get(parent)) {
    int temp = heap.get(i);
    heap.set(i, heap.get(parent));
    heap.set(parent, temp);
    i = parent;
    parent = (i-1)/2;
  }
}

Deletion

Deletion is the process of removing an item from the heap. To do this, we first need to find the item we want to remove. Once the item is found, we need to replace it with the last item in the heap. Then, we need to compare the new item with its parent and children nodes and swap it with the smallest item.

public void delete(int item) {
  // Get the size of the heap
  int n = heap.size();
  
  // Find the item we want to delete
  int i = 0;
  for (int j = 0; j < n; j++) {
    if (heap.get(j) == item) {
      i = j;
      break;
    }
  }
  
  // Replace the item with the last item in the heap
  heap.set(i, heap.get(n-1));
  heap.remove(n-1);
  n--;
  
  // Compare the item to its parent and children nodes
  int parent = (i-1)/2;
  int left = 2*i + 1;
  int right = 2*i + 2;
  
  // Swap the item with the smallest item
  while (i > 0 && heap.get(i) < heap.get(parent)) {
    int temp = heap.get(i);
    heap.set(i, heap.get(parent));
    heap.set(parent, temp);
    i = parent;
    parent = (i-1)/2;
  }
  
  while (left < n && (heap.get(i) > heap.get(left) || 
    heap.get(i) > heap.get(right))) {
    if (heap.get(left) < heap.get(right)) {
      int temp = heap.get(i);
      heap.set(i, heap.get(left));
      heap.set(left, temp);
      i = left;
    }
    else {
      int temp = heap.get(i);
      heap.set(i, heap.get(right));
      heap.set(right, temp);
      i = right;
    }
    left = 2*i + 1;
    right = 2*i + 2;
  }
}

Access

Access is the process of retrieving an item from the heap. To do this, we simply need to retrieve the item at the root node. This operation can be done in constant time, as the root node is always the smallest item in the heap.

public int access() {
  return heap.get(0);
}

Search

Search is the process of finding an item in the heap. To do this, we need to traverse the heap, comparing each item to the item we are looking for. This operation can also be done in constant time, as the root node is always the smallest item in the heap.

public int search(int item) {
  // Traverse the heap, comparing each item to the item we are looking for
  for (int i = 0; i < heap.size(); i++) {
    if (heap.get(i) == item) {
      return i;
    }
  }
  
  // If the item is not found, return -1
  return -1;
}

Conclusion

In this article, we have discussed the features of a min heap, how it works, and the time and space complexities for the operations. We have also provided Java code examples to illustrate each operation. A min heap is a type of binary tree that follows the heap property, which states that the value of any node is greater than or equal to the value of its parent node. The operations with a min heap are insertion, deletion, and search, and all of these operations can be performed in time proportional to the height of the tree, which is log n, where n is the number of items in the tree. The space complexity for a min heap is O(n), where n is the number of items in the tree.

Exercises

public void deleteRoot() {
  // Get the size of the heap
  int n = heap.size();
  
  // Replace the root node with the last item in the heap
  heap.set(0, heap.get(n-1));
  heap.remove(n-1);
  n--;
  
  // Compare the root node to its parent and children nodes
  int i = 0;
  int parent = (i-1)/2;
  int left = 2*i + 1;
  int right = 2*i + 2;
  
  // Swap the root node with the smallest item
  while (i > 0 && heap.get(i) < heap.get(parent)) {
    int temp = heap.get(i);
    heap.set(i, heap.get(parent));
    heap.set(parent, temp);
    i = parent;
    parent = (i-1)/2;
  }
  
  while (left < n && (heap.get(i) > heap.get(left) || 
    heap.get(i) > heap.get(right))) {
    if (heap.get(left) < heap.get(right)) {
      int temp = heap.get(i);
      heap.set(i, heap.get(left));
      heap.set(left, temp);
      i = left;
    }
    else {
      int temp = heap.get(i);
      heap.set(i, heap.get(right));
      heap.set(right, temp);
      i = right;
    }
    left = 2*i + 1;
    right = 2*i + 2;
  }
}

public int findMin() {
  return heap.get(0);
}

public int findMax() {
  // Get the size of the heap
  int n = heap.size();
  
  // Initialize the max to the first item in the heap
  int max = heap.get(0);
  
  // Traverse the heap, comparing each item to the max
  for (int i = 1; i < n; i++) {
    if (heap.get(i) > max) {
      max = heap.get(i);
    }
  }
  
  return max;
}

public int findHeight() {
  // Get the size of the heap
  int n = heap.size();
  
  // Initialize the height to 0
  int height = 0;
  
  // Traverse the heap, increasing the height each time
  // we reach a new level
  int i = 0;
  while (i < n) {
    height++;
    i = 2*i + 1;
  }
  
  return height;
}

public void printLevelOrder() {
  // Get the size of the heap
  int n = heap.size();
  
  // Initialize the level to 0
  int level = 0;
  
  // Traverse the heap, printing each item at the current level
  int i = 0;
  while (i < n) {
    System.out.print(heap.get(i) + " ");
    i++;
    if (i == Math.pow(2, level)) {
      System.out.println();
      level++;
    }
  }
}