## What is Tree?

In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

A *tree* is a nonlinear *data structure*, compared to arrays, linked lists, stacks and queues which are linear *data structures*. A *tree* can be empty with no nodes or a *tree* is a *structure* consisting of one node called the root and zero or one or more subtrees.

## What is Heap?

A *Heap* is a special Tree-based data structure in which the tree is a complete binary tree. Any node of a heap must satisfy the heap property. For example in maxheap any parent node have a greater element then any element of child.

## Types of Heap

There are two types of heap. They are:

- Max Heap
- Min Heap

### Max Heap

Max heap is a complete binary tree where each node has a greater value then any of its children.

### Min Heap

Min heap is a complete binary tree where each node have a smaller value than any of its children.

## Difference Between Binary Search Tree & Heap

Binary Search Tree | Heap |

A tree is said to be Binary Search Tree if all node have a greater vale than left node and smaller value than right node. | A tree is said to be Heap if all node have a greater value than its children (max heap) or smaller value than its children (min heap). |

Binary Search Tree maybe complete or not. | Heap is always a complete tree. |

Binary Search Tree is easy to search an element. | Heap is easy to insert or delete an element from the list. |

Time complexity for Binary Search Tree is O(h). Where h is the height or depth of the tree. | Time complexity for Heap is O(log(n)). Where n is the number of nodes in the heap. |

## Delete from Heap

To delete an element from heap we need to follow 2 steps:

- Delete the element and take the last element at at the place of deleted element. Replace the element to delete with last element and decrease the size of heap n to n-1.
- Recursively test and swap the replaced value with next/child nodes as long as the heap property is not satisfied. For max heap swap if replaced value is smaller than next/child nodes. For min heap swap if replaced value is greater than next/child nodes.

## C++ Code to Delete from Max Heap

```
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,i,m; //n is no of elements,i is normal integer and m is used to save i
cout<<"How Much Elements are in Your Heap: ";
cin>>n;
long H[n+5],Delete; //H is Array to take input the elements of heap
cout<<"Enter All Elements of Heap in Sequential Representation:"<<endl;
for(i=1;i<=n;i++){
cin>>H[i];
}
cout<<endl;
cout<<"Before Deletion:"<<endl;
for(i=1;i<=n;i++){
cout<<H[i]<<" ";
}
cout<<endl<<endl;
cout<<"What will you Delete Now: ";
cin>>Delete; //Delete will be deleted from the heap
cout<<endl;
for(i=1;i<=n;i++)if(H[i]==Delete){ //For loop to take last element at deleted position
m=i;
H[i]=H[n];
}
for(i=m;i<n/2;i){ //For loop to bring the last element at exact position
if(H[2*i]>H[(2*i)+1]&&H[2*i]>H[i]){
swap(H[i],H[2*i]);
i=2*i;
cout<<" B "<<i;
}
else if(H[2*i]<H[(2*i)+1]&&H[(2*i)+1]>H[i]){
swap(H[i],H[(2*i)+1]);
i=(2*i)+1;
}
else break;
}
n=n-1; //Decreasing Number of element or deleting last element
cout<<"After Deletion:"<<endl;
for(i=1;i<=n;i++){
cout<<H[i]<<" ";
}
cout<<endl;
return 0;
}
```

## C++ Code to Delete from Min Heap

```
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,i,m; //n is no of elements,i is normal integer and m is used to save i
cout<<"How Much Elements are in Your Heap: ";
cin>>n;
long H[n+5],Delete; //H is Array to take input the elements of heap
cout<<"Enter All Elements of Heap in Sequential Representation:"<<endl;
for(i=1;i<=n;i++){
cin>>H[i];
}
cout<<endl;
cout<<"Before Deletion:"<<endl;
for(i=1;i<=n;i++){
cout<<H[i]<<" ";
}
cout<<endl<<endl;
cout<<"What will you Delete Now: ";
cin>>Delete; //Delete will be deleted from the heap
cout<<endl;
for(i=1;i<=n;i++)if(H[i]==Delete){ //For loop to take last element at deleted position
m=i;
H[i]=H[n];
}
for(i=m;i<n/2;i){ //For loop to bring the last element at exact position
if(H[2*i]<H[(2*i)+1]&&H[2*i]<H[i]){
swap(H[i],H[2*i]);
i=2*i;
cout<<" B "<<i;
}
else if(H[2*i]>H[(2*i)+1]&&H[(2*i)+1]<H[i]){
swap(H[i],H[(2*i)+1]);
i=(2*i)+1;
}
else break;
}
n=n-1; //Decreasing Number of element or deleting last element
cout<<"After Deletion:"<<endl;
for(i=1;i<=n;i++){
cout<<H[i]<<" ";
}
cout<<endl;
return 0;
}
```

Hope your experience with this tutorial is quite good. Comment how do you feel about this tutorial. If you have any confusion you can also comment here. Subscribe for latest posts.