A binary heap is a heap data structure created using a binary tree.

binary tree has two rules –

- Binary Heap has to be a complete binary tree at all levels except the last level. This is called a
.*shape property* - All nodes are either greater than equal to (
) or less than equal to (*Max-Heap*) to each of its child nodes. This is called*Min-Heap*.*heap property*

**Implementation:**

- Use an array to store the data.
- Start storing from index 1, not 0.
- For any given node at position i:
- Its
**Left Child**is atif available.*[2*i]* - Its
**Right Child**is atif available.*[2*i+1]* - Its
**Parent Node**is atif available.*[i/2]*

Heap Majorly has 3 operations –

- Insert Operation
- Delete Operation
- Extract-Min (OR Extract-Max)

**Insert Operation:**

- Add the element at the bottom leaf of the Heap.
- Perform the Bubble-Up operation.
- All Insert Operations must perform the
operation(*bubble-up*)*it is also called as up-heap, percolate-up, sift-up, trickle-up, heapify-up, or cascade-up*

**Extract-Min OR Extract-Max Operation:**

- Take out the element from the root.( it will be minimum in case of Min-Heap and maximum in case of Max-Heap).
- Take out the last element from the last level from the heap and replace the root with the element.
- Perform Sink-Down
- All delete operations must perform Sink-Down Operation ( also known as
*bubble-down*,*percolate-down*,*sift-down*,*trickle-down*,*heapify-down*,*cascade-down).*

**Sink-Down Operation:**

- If the replaced element is greater than any of its child node in case of Min-Heap OR smaller than any if its child node in case of Max-Heap, swap the element with its smallest child(Min-Heap) or with its greatest child(Max-Heap).
- Keep repeating the above step, if the node reaches its correct position, STOP.

**Delete Operation:**

- Find the index for the element to be deleted.
- Take out the last element from the last level from the heap and replace the index with this element .
- Perform
*Sink-Down*

**Time and Space Complexity:**

Space | O(n) |

Search | O(n) |

Insert | O(log n) |

Delete | O(log n) |

**Complete Code for Min-Heap:**

## Java

public class minHeap { public int capacity; public int [] mH; public int currentSize; public minHeap(int capacity){ this.capacity=capacity; mH = new int [capacity+1]; currentSize =0; } public void createHeap(int [] arrA){ if(arrA.length>0){ for(int i=0;i<arrA.length;i++){ insert(arrA[i]); } } } public void display(){ for(int i=1;i<mH.length;i++){ System.out.print(" " + mH[i]); } System.out.println(""); } public void insert(int x) { if(currentSize==capacity){ System.out.println("heap is full"); return; } currentSize++; int idx = currentSize; mH[idx] = x; bubbleUp(idx); } public void bubbleUp(int pos) { int parentIdx = pos/2; int currentIdx = pos; while (currentIdx > 0 && mH[parentIdx] > mH[currentIdx]) { swap(currentIdx,parentIdx); currentIdx = parentIdx; parentIdx = parentIdx/2; } } public int extractMin() { int min = mH[1]; mH[1] = mH[currentSize]; mH[currentSize] = 0; sinkDown(1); currentSize--; return min; } public void sinkDown(int k) { int smallest = k; int leftChildIdx = 2 * k; int rightChildIdx = 2 * k+1; if (leftChildIdx < heapSize() && mH[smallest] > mH[leftChildIdx]) { smallest = leftChildIdx; } if (rightChildIdx < heapSize() && mH[smallest] > mH[rightChildIdx]) { smallest = rightChildIdx; } if (smallest != k) { swap(k, smallest); sinkDown(smallest); } } public void swap(int a, int b) { int temp = mH[a]; mH[a] = mH[b]; mH[b] = temp; } public boolean isEmpty() { return currentSize == 0; } public int heapSize(){ return currentSize; } public static void main(String args[]){ int arrA [] = {3,2,1,7,8,4,10,16,12}; System.out.print("Original Array : "); for(int i=0;i<arrA.length;i++){ System.out.print(" " + arrA[i]); } minHeap m = new minHeap(arrA.length); System.out.print("\nMin-Heap : "); m.createHeap(arrA); m.display(); System.out.print("Extract Min :"); for(int i=0;i<arrA.length;i++){ System.out.print(" " + m.extractMin()); } } }

**Output:**

Original Array : 3 2 1 7 8 4 10 16 12 Min-Heap : 1 3 2 7 8 4 10 16 12 Sorted: 1 3 2 12 8 4 10 16 0