Min Heap Construction

Min heap is a binary tree-like structure, which satisfies the following conditions:

1. Each node value is lesser than the children's.

2. It should be a complete tree, if not then the extra children should be added on the left leaf nodes.

Min heap is in no way completely sorted but the root will always have the smallest value.

Some calculations to represent min heap as an array:

• Current Node: i

• ChildOne: 2i + 1

• ChildTwo: 2i + 2

• ParentNode: floor((i - 1)/2)

There are 5 methods to be considered:

1. Build Heap {O(N)} - This method builds a heap from any provided array. The way we do that is called siftDown on every parent node starting from the last parent node.

2. SiftDown {O(logN))} - This Method will Shift the element down in the heap. The way we do it is that we compare the node value with the children's node, swap the node with the least value of both the children and keep swapping till the node is the smallest of the children.

3. SiftUp {O(logN))} - This Method will shift the element up in the heap. The way we do that is simply to compare the element with the parent, if the parent is greater than the current node, then we swap and keep swapping till the condition becomes false.

4. Insert {O(logN))} - As discussed in the definition, the node should be added in the leftmost leaf, and then SiftUp can be called to adjust the value.

5. Remove {O(logN))} - First the nodeToBeRemoved should be swapped with the last node, then just removed, now SiftDown can be called on the swapped node to adjust its position in the heap.

Code Implementation:

import java.util.*;
class Program {
  static class MinHeap {
    List<Integer> heap = new ArrayList<Integer>();

    public MinHeap(List<Integer> array) {
      heap = buildHeap(array);
    }

    public List<Integer> buildHeap(List<Integer> array) {
      int firstParentIdx = array.size() - 2 / 2;
      for (int currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
        this.siftDown(currentIdx, array.size() - 1, array);
      }
      return array;
    }

    public void siftDown(int currentIdx, int endIdx, List<Integer> heap) {
      int childOneIdx = (currentIdx * 2) + 1;
      int idxToSwap = -1;
      while (childOneIdx <= endIdx) {
        int childTwoIdx = (currentIdx * 2) + 2;
        if (childTwoIdx <= endIdx && heap.get(childTwoIdx) < heap.get(childOneIdx)){
          idxToSwap = childTwoIdx;
        } else {
          idxToSwap = childOneIdx;
        }

        if (heap.get(idxToSwap) < heap.get(currentIdx)) {
          this.swap(idxToSwap, currentIdx, heap);
          currentIdx = idxToSwap;
          childOneIdx = currentIdx * 2 + 1;
        }
        else {
          break;
        }
      }
    }

    public void siftUp(int currentIdx, List<Integer> heap) {
      int parentIdx = (currentIdx - 1) / 2;
      while (currentIdx > 0 && heap.get(currentIdx) < heap.get(parentIdx)) {
        this.swap(currentIdx, parentIdx, heap);
        currentIdx = parentIdx;
        parentIdx = (currentIdx - 1) / 2;
      }
    }

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

    public int remove() {
      this.swap(0, this.heap.size() - 1, this.heap);
      int removedValue = this.heap.remove(this.heap.size() - 1);
      this.siftDown(0, this.heap.size() - 1, this.heap);
      return removedValue;
    }

    public void insert(int value) {
      this.heap.add(value);
      this.siftUp(this.heap.size() - 1, this.heap);
    }
    public void swap(int i, int j, List<Integer> heap) {
      int atI = heap.get(i);
      int atJ = heap.get(j);
      heap.set(i, atJ);
      heap.set(j, atI);
    }
  }
}

Similar way Max heap can be contructed just by changing the < to > everywhere in the code.