Heap Data Structure

A heap is a specialized tree-based data structure that satisfies the heap property. The heap property specifies the ordering between parent and child nodes.

A heap can be either a max heap or a min heap:

• In a max heap, the parent node is always greater than or equal to its child nodes.
• In a min heap, the parent node is always smaller than or equal to its child nodes.

Heaps are commonly used to implement priority queues, where the heap property ensures that the highest (or lowest) priority element is always at the root of the heap.

Operations

The main operations supported by a heap are:

• Insertion: Adding an element to the heap while maintaining the heap property.
• Deletion: Removing the root element from the heap while maintaining the heap property.
• Heapify: Restoring the heap property by rearranging the elements of the heap after an operation has violated the property.

Java Implementation of Min Heap

Here's a Java implementation of a min heap, including operations for insertion and heapify:

1// MinHeap class
2class MinHeap {
3  private int[] heap;
4  private int size;
5  private int maxSize;
6
7  public MinHeap(int maxSize) {
8    this.maxSize = maxSize;
9    this.size = 0;
10    this.heap = new int[maxSize];
11  }
12
13  // Other helper methods...
14
15  public void insert(int element) {
16    // Insertion logic...
17  }
18
19  public void heapify(int pos) {
20    // Heapify logic...
21  }
22}

xxxxxxxxxx

}

class Main {

  public static void main(String[] args) {

    // Replace with your Java logic here

    // Example: Creating a min-heap

    MinHeap minHeap = new MinHeap(10);

    minHeap.insert(4);

    minHeap.insert(3);

    minHeap.insert(7);

    minHeap.insert(6);

    minHeap.insert(10);

    minHeap.insert(1);

    minHeap.insert(2);

    System.out.println("Heap:");

    minHeap.printHeap();

  }

}

​

// MinHeap class

class MinHeap {

  private int[] heap;

  private int size;

  private int maxSize;

​

  public MinHeap(int maxSize) {

    this.maxSize = maxSize;

    this.size = 0;

    this.heap = new int[maxSize];

  }