Heap is a Data Structure that follows the following: It should be a Complete Binary Tree(CBT) and has a “Heap Order Property”
A complete Binary Tree (CBT) is a binary tree where every level is completely filled except the last level and the nodes are always added from the left or you can say is left-leaning.

There are two types of Heap
- Max Heap
- Min Heap
Max Heap
Child nodes value should be less than the root.

Min Heap
The child nodes will be greater than the root

Complete Binary Tree (BST) and array relation
At any ith index
left child -> ( 2 * i)index
right child -> (2 * i) + 1 index
Heap implemented using array
public class Heap { int[] arr = new int[100]; int size = 0; /** * Algorithm * - Insert at end * - Move element to correct position * - compare with parent and swap */ void insert(int val){ size = size + 1; int index = size; arr[index] = val; while(index > 1){ int parent = index / 2; if(arr[parent] < arr[index]){ swap(parent, index); index = parent; }else{ return; } } } /** * Algorithm * - Put last elemet to the root (first element) * - remove last node * - Propogate root note to its correct location */ void delete() { if (size == 0) { System.out.println("Heap empty"); return; } arr[1] = arr[size]; size--; int i = 1; while (i < size) { { int leftIndex = 2 * i; int rightIndex = 2 * i + 1; if (leftIndex < size && arr[i] < arr[leftIndex]) { swap(i, leftIndex); i = leftIndex; } else if (rightIndex < size && arr[i] < rightIndex) { swap(i, rightIndex); i = rightIndex; } else { return; } } } } void swap(int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void display(){ for(int i = 1; i <= size; i++){ System.out.print(arr[i] + " "); } } /** * CBT (Complete Binary Tree) * (n/2 + 1) -> n */ void heapify(int[] arr, int n, int i){ int largest = i; int left = 2 * i; int right = 2 * i + 1; if(left < n && arr[largest] < arr[left]){ largest = left; } if(right < n && arr[largest] < arr[right]){ largest = right; } if(largest != i){ swap(i, largest); heapify(arr, n, largest); } } public static void main(String[] args) { Heap heap = new Heap(); heap.insert(50); heap.insert(2); heap.insert(40); heap.insert(30); heap.insert(20); heap.insert(10); heap.display(); } }