Heap in JAVA

Objective: To understand everything about Heap.

1. Heap memory

   

Dynamic Allocation: The heap memory allows for dynamic allocation and deallocation of objects.

• This is a runtime data area of the Java Virtual Machine (JVM)

• where objects are stored during program execution.

• Objects created using the “new” keyword are allocated space in the heap memory.

• It's a shared memory area, accessible by all threads running within the Java application.

• The garbage collector (GC) automatically manages memory allocation and deallocation for objects in the heap.

  & is responsible for reclaiming memory occupied by objects that are no longer needed.

• High heap memory usage can indicate potential memory leaks or an application requiring significant memory.

More about Garbage Collection:

• It is related to the management of Java heap memory.

• Allocation and Object Lifecycles: When objects are created in Java, memory is allocated on the heap to store them.

  So long as objects are reachable and referenced by the program, they are considered live objects.

  However, when objects become unreachable or no longer referenced, they are eligible for garbage collection.

• By reclaiming memory occupied by garbage objects,

  The garbage collector helps prevent memory leaks, optimizes memory usage, and ensures efficient utilization of the Java heap memory.

• Since garbage collection consumes CPU,

  Low Java heap memory can manifest as excessive CPU usage, and a shortage of CPU may be a symptom.

Conclusion:

Managing and optimizing the usage of heap memory is important for ensuring efficient memory utilization and preventing issues like memory leaks or excessive memory consumption.

2. Heap Data Structure

   

• The most fundamental data structure is called a Heap.

• It is mainly used to represent a priority queue.

• It is represented as a Complete Binary Tree - a tree structure where each node has a maximum of two child nodes.

Organization of Heaps:

• Implemented using Arrays.

import java.util.ArrayList;

class MinHeap {
    private ArrayList<Integer> heap;
public MinHeap() {//Constructor
        heap = new ArrayList<>();
    }
//OR
class MaxHeap {
    private ArrayList<Integer> heap;
public MaxHeap() {//Constructor
        heap = new ArrayList<>();
    }

where,

• The root is at index 0.

• For any node at index i,

  : Its left child is at index: 2*i + 1

  : Its right child is at index: 2*i + 2

  : Its parent is at index (i - 1) / 2

private int parent(int i) {
        return (i - 1) / 2;
    }
private int leftChild(int i) {
        return 2 * i + 1;
    }
private int rightChild(int i) {
        return 2 * i + 2;
    }
// Swaps the elements at indices i and j

private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

Heap Diagram:

Implementation in Java:

• insert: Adds a new element and restores the heap property.

  TC: O(log n)

• Extract: Removes and returns the root element, then restores the heap property.

  TC: O(log n)

• heapify: Re-balances the heap after an operation.

  TC: O(n)-because half of the nodes are leaves and require little or no adjustment.

Code To Implementation Min Heap:

• Binary heap where the parent node is always less than or equal to its child nodes.

• The smallest element is always at the root of the heap.

    //INSERT
    public void insert(int value) {
          heap.add(value); 
          int currentIndex = heap.size() - 1;
          while (currentIndex > 0 && heap.get(currentIndex) < heap.get(parent(currentIndex))) {
                 swap(currentIndex, parent(currentIndex)); 
                 currentIndex = parent(currentIndex); 
            }
    }
  

    //Extract 
    //Return Min Value from heap
    public int extractMin() {
            //for empty heap
            if (heap.isEmpty()) {
                throw new RuntimeException("Heap is empty");
            }
           //minimum value - at root
           int min = heap.get(0); 
           //remove Last element
           int lastElement = heap.remove(heap.size() - 1); 
  
           if (!heap.isEmpty()) {
                // Move the last element to the root
                heap.set(0, lastElement); 
  
                // Bubble down to restore heap property
                int currentIndex = 0;
                while (true) {
                    int left = leftChild(currentIndex);
                    int right = rightChild(currentIndex);
                    int smallest = currentIndex;
  
                    // Find the smallest value among current, left child, and right child
                    if (left < heap.size() && heap.get(left) < heap.get(smallest)) {
                        smallest = left;
                    }
  
                    if (right < heap.size() && heap.get(right) < heap.get(smallest)) {
                        smallest = right;
                    }
  
                    if (smallest == currentIndex) {
                        // Heap property is restored
                        break; 
                   }
                 // Swap with the smallest child
                  swap(currentIndex, smallest); 
                    // Move down to the smallest child's index
                    currentIndex = smallest; 
                }
            }
  
            // Return the minimum value
            return min; 
        }
    // Checks if the heap is empty
        public boolean isEmpty() {
            return heap.isEmpty();
        }
  

    public class HeapExample {
        public static void main(String[] args) {
            MinHeap minHeap = new MinHeap();
  
            // Insert values into the min heap
  
            minHeap.insert(6);
            minHeap.insert(5);
            minHeap.insert(1);
            minHeap.insert(2);
            minHeap.insert(7);
  
            // Extract and print the minimum values from the heap
            System.out.println("Extracted Min: " + minHeap.extractMin());
            System.out.println("Extracted Min: " + minHeap.extractMin());
        }
    }
    //Output:
    //Extracted Min: 1 //after 1 is removed next minimum is 2
    //Extracted Min: 2
  

  

• Code To Implementation Max Heap:

binary heap where the parent node is always greater than or equal to its child nodes.

The largest element is always at the root of the heap

//INSERT
public void insert(int value) {
      heap.add(value); 
      int currentIndex = heap.size() - 1;
      while (currentIndex > 0 && heap.get(currentIndex) > heap.get(parent(currentIndex))) {
             swap(currentIndex, parent(currentIndex)); 
             currentIndex = parent(currentIndex); 
        }
}

//Extract 
//Return Max Value from heap
public int extractMax() {
        //for empty heap
        if (heap.isEmpty()) {
            throw new RuntimeException("Heap is empty");
        }
       //maximum value - at root
       int max = heap.get(0); 
       //remove Last element
       int lastElement = heap.remove(heap.size() - 1); 

       if (!heap.isEmpty()) {
            // Move the last element to the root
            heap.set(0, lastElement); 

            // Bubble down to restore heap property
            int currentIndex = 0;
            while (true) {
                int left = leftChild(currentIndex);
                int right = rightChild(currentIndex);
                int largest = currentIndex;

                // Find the largest value among current, left child, and right child
                if (left < heap.size() && heap.get(left) > heap.get(smallest)) {
                   largest = left;
                }

                if (right < heap.size() && heap.get(right) > heap.get(smallest)) {
                    largest = right;
                }

                if (largest == currentIndex) {
                    // Heap property is restored
                    break; 
               }
             // Swap with the largest child
              swap(currentIndex, largest); 
                // Move down to the smallest child's index
                currentIndex = largest; 
            }
        }

        // Return the maximum value
        return max; 
    }
// Checks if the heap is empty
    public boolean isEmpty() {
        return heap.isEmpty();
    }

public class HeapExample {
    public static void main(String[] args) {
        MaxHeapminHeap = new MaxHeap();

        // Insert values into the min heap

        maxHeap.insert(6);
        maxHeap.insert(5);
        maxHeap.insert(1);
        maxHeap.insert(2);
        maxHeap.insert(7);

        // Extract and print the minimum values from the heap
        System.out.println("Extracted Max: " + maxHeap.extractMax());
        System.out.println("Extracted Max: " + maxHeap.extractMax());
    }
}
//Output:
//Extracted Max: 7 //after 7 is removed next maximum is 6
//Extracted Max: 6

Explanation:

For Max-Value Extraction, and similar for Min-Value

Applications of Heaps:

• Priority Queues: For efficient priority queue operations.

• Heap Sort: A Sorting Algorithm

• Graph Algorithms: Dijkstra's algorithm and Prim's algorithm - for efficient vertex extraction.

• Median Maintenance: In scenarios where the median needs to be maintained dynamically.

Conclusion:

• Heaps are versatile data structures with a wide range of applications.

• Their efficient insertion and extraction operations make them ideal for implementing priority queues and optimizing graph algorithms.

• With a clear understanding of how heaps are structured and implemented in Java, you can leverage them in various problem-solving scenarios.