# Binary Min-Max Heap Implementation

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

binary tree has two rules –

1. Binary Heap has to be a complete binary tree at all levels except the last level. This is called a shape property.
2. All nodes are either greater than equal to (Max-Heap) or less than equal to (Min-Heap) to each of its child nodes. This is called 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 at [2*i] if available.
• Its Right Child is at [2*i+1] if available.
• Its Parent Node is at [i/2]if available.

Heap Majorly has 3 operations –

1. Insert Operation
2. Delete Operation
3. 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 bubble-up operation(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:

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;
mH = 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
```
{"ft_lang_label":"__label__en","ft_lang_prob":0.65464824,"math_prob":0.96000403,"size":4021,"snap":"2021-31-2021-39","text_gpt3_token_len":1135,"char_repetition_ratio":0.124471,"word_repetition_ratio":0.056514915,"special_character_ratio":0.30216363,"punctuation_ratio":0.17317073,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.95873326,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-23T12:04:44Z\",\"WARC-Record-ID\":\"<urn:uuid:9547a4e8-7e72-44ba-a1a6-4b8edb1d10c1>\",\"Content-Length\":\"77974\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4134fa6e-285b-4dd4-b357-b9b89e80c3e0>\",\"WARC-Concurrent-To\":\"<urn:uuid:1444064b-d44c-494c-9de1-47de7e83a523>\",\"WARC-IP-Address\":\"104.21.80.108\",\"WARC-Target-URI\":\"https://algorithms.tutorialhorizon.com/binary-min-max-heap/\",\"WARC-Payload-Digest\":\"sha1:7HA7RGVRPKWN7AOPS3PXKI6PM3CXUSE7\",\"WARC-Block-Digest\":\"sha1:UA4FG44LI5YFMV5MHKR3CFQPV4HSROQT\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780057421.82_warc_CC-MAIN-20210923104706-20210923134706-00396.warc.gz\"}"}