//Adjacency Matrix

include <iostream>

using namespace std;

int main(){ int n,m; cin>>n>>m; int adjm[n+1][n+1]={0}; for(int i=0;i<m;i++){ int u,v; cin>>u>>v; adjm[u][v]=1; adjm[v][u]=1;

}
cout<<"Adjacency Matrix :"<<endl;
for(int i=1;i<n+1;i++){
    for(int j=1;j<n+1;j++){
        cout<<adjm[i][j]<<" ";
    }
    cout<<endl;
}

}

// Adjacency List

include<iostream>

include<bits/stdc++.h>

using namespace std; const int N=1e5+2;

vector <int> adj[N];

int main(){ int n,m; cin>>n>>m;

for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}

cout<<"adjacency list :"<<endl;

for(int i=1;i<n+1;i++){

    cout<<i<<"->";
    for(auto x : adj[i]){
        cout<<x<<" ";

    }
    cout<<endl;
}

}

// BFS

include<iostream>

include<bits/stdc++.h>

using namespace std; const int N=1e5+2;

vector <int> adj[N]; bool vis[N]={0};

int main(){ int n,m; cin>>n>>m;

for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);

}

queue<int> q ;

q.push(1);
vis[1]=true;

while(!q.empty()){
    int node = q.front();
    q.pop();
    cout<<node<<endl;
    for(int i=1;i<n+1;i++){

    for(auto x : adj[i]){
        if(!vis[x]){
            vis[x]=1;
            q.push(x);
        }

      }
    }
}

}

//DFS

include<iostream>

include<bits/stdc++.h>

using namespace std; const int N=1e5+2;

vector <int> adj[N]; bool vis[N]={0};

void dfs(int node){ vis[node]=1; //preorder cout<<node<<" ";

//inorder
vector <int> :: iterator it;
for(it =adj[node].begin();it!=adj[node].end();it++){

        if(vis[*it]);
        else{
            dfs(*it);

        }

}

//postorder

}

int main(){

int m,n;
cin>>n>>m;
for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

dfs(1);

}

//Topological sort //cycle detect in directed graph

include<iostream>

include<bits/stdc++.h>

using namespace std;

int main(){

int n,m;
int cnt;
cnt=0;
cin>>n>>m;
vector <vector<int>> adj(n);
vector <int> ind(n,0);
for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    ind[v]++;
}

queue <int> pq ;

for(int i=0;i<n;i++){

    if(ind[i]==0){
        pq.push(i);
    }

}

while(!pq.empty()){
    cnt++;
    int x = pq.front();
    pq.pop();
    cout<<x<<" ";
    for(auto it : adj[x]){
        ind[it]--;
        if(ind[it]==0){
            pq.push(it);
        }
    }

}
if(cnt!=n){ 
  cout<<"graph is cyclic";
}
else{
    cout<<"graph is acyclic";
}

}

BINARY TREE TRAVERSAL

// Tree traversal in C++

include <iostream>

using namespace std;

struct Node { int data; struct Node left, right; Node(int data) { this->data = data; left = right = NULL; } };

// Preorder traversal void preorderTraversal(struct Node* node) { if (node == NULL) return;

cout << node->data << "->"; preorderTraversal(node->left); preorderTraversal(node->right); }

// Postorder traversal void postorderTraversal(struct Node* node) { if (node == NULL) return;

postorderTraversal(node->left); postorderTraversal(node->right); cout << node->data << "->"; }

// Inorder traversal void inorderTraversal(struct Node* node) { if (node == NULL) return;

inorderTraversal(node->left); cout << node->data << "->"; inorderTraversal(node->right); }

int main() { struct Node* root = new Node(1); root->left = new Node(12); root->right = new Node(9); root->left->left = new Node(5); root->left->right = new Node(6);

cout << "Inorder traversal "; inorderTraversal(root);

cout << "\nPreorder traversal "; preorderTraversal(root);

cout << "\nPostorder traversal "; postorderTraversal(root);

}

BALANCED BINARY TREE

// Checking if a binary tree is height balanced in C++

include

using namespace std;

define bool int

class node { public: int item; node left; node right; };

// Create anew node node newNode(int item) { node Node = new node(); Node->item = item; Node->left = NULL; Node->right = NULL;

return (Node); }

// Check height balance bool checkHeightBalance(node root, int height) { // Check for emptiness int leftHeight = 0, rightHeight = 0;

int l = 0, r = 0;

if (root == NULL) { *height = 0; return 1; }

l = checkHeightBalance(root->left, &leftHeight); r = checkHeightBalance(root->right, &rightHeight);

*height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;

if (std::abs(leftHeight - rightHeight >= 2)) return 0;

else return l && r; }

int main() { int height = 0;

node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5);

if (checkHeightBalance(root, &height)) cout << "The tree is balanced"; else cout << "The tree is not balanced"; }

BINARY SEARCH TREE OPERATIONS (INSERTION AND DELETION)

// Binary Search Tree operations in C++

include <iostream>

using namespace std;

struct node { int key; struct node left, right; };

// Create a node struct node newNode(int item) { struct node temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; }

// Inorder Traversal void inorder(struct node *root) { if (root != NULL) { // Traverse left inorder(root->left);

// Traverse root
cout << root->key << " -> ";

// Traverse right
inorder(root->right);

} }

// Insert a node struct node insert(struct node node, int key) { // Return a new node if the tree is empty if (node == NULL) return newNode(key);

// Traverse to the right place and insert the node if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key);

return node; }

// Find the inorder successor struct node minValueNode(struct node node) { struct node *current = node;

// Find the leftmost leaf while (current && current->left != NULL) current = current->left;

return current; }

// Deleting a node struct node deleteNode(struct node root, int key) { // Return if the tree is empty if (root == NULL) return root;

// Find the node to be deleted if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { // If the node is with only one child or no child if (root->left == NULL) { struct node temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct node temp = root->left; free(root); return temp; }

// If the node has two children
struct node *temp = minValueNode(root->right);

// Place the inorder successor in position of the node to be deleted
root->key = temp->key;

// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);

} return root; }

// Driver code int main() { struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4);

cout << "Inorder traversal: "; inorder(root);

cout << "\nAfter deleting 10\n"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); }

AVL TREE AND ROTATIONS

// AVL tree implementation in C++

include <iostream>

using namespace std;

class Node { public: int key; Node left; Node right; int height; };

int max(int a, int b);

// Calculate height int height(Node *N) { if (N == NULL) return 0; return N->height; }

int max(int a, int b) { return (a > b) ? a : b; }

// New node creation Node newNode(int key) { Node node = new Node(); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; return (node); }

// Rotate right Node rightRotate(Node y) { Node x = y->left; Node T2 = x->right; x->right = y; y->left = T2; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x; }

// Rotate left Node leftRotate(Node x) { Node y = x->right; Node T2 = y->left; y->left = x; x->right = T2; x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; return y; }

// Get the balance factor of each node int getBalanceFactor(Node *N) { if (N == NULL) return 0; return height(N->left) - height(N->right); }

// Insert a node Node insertNode(Node node, int key) { // Find the correct postion and insert the node if (node == NULL) return (newNode(key)); if (key < node->key) node->left = insertNode(node->left, key); else if (key > node->key) node->right = insertNode(node->right, key); else return node;

// Update the balance factor of each node and // balance the tree node->height = 1 + max(height(node->left), height(node->right)); int balanceFactor = getBalanceFactor(node); if (balanceFactor > 1) { if (key < node->left->key) { return rightRotate(node); } else if (key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } } if (balanceFactor < -1) { if (key > node->right->key) { return leftRotate(node); } else if (key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); } } return node; }

// Node with minimum value Node nodeWithMimumValue(Node node) { Node *current = node; while (current->left != NULL) current = current->left; return current; }

// Delete a node Node deleteNode(Node root, int key) { // Find the node and delete it if (root == NULL) return root; if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { if ((root->left == NULL) || (root->right == NULL)) { Node temp = root->left ? root->left : root->right; if (temp == NULL) { temp = root; root = NULL; } else root = temp; free(temp); } else { Node temp = nodeWithMimumValue(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); } }

if (root == NULL) return root;

// Update the balance factor of each node and // balance the tree root->height = 1 + max(height(root->left), height(root->right)); int balanceFactor = getBalanceFactor(root); if (balanceFactor > 1) { if (getBalanceFactor(root->left) >= 0) { return rightRotate(root); } else { root->left = leftRotate(root->left); return rightRotate(root); } } if (balanceFactor < -1) { if (getBalanceFactor(root->right) <= 0) { return leftRotate(root); } else { root->right = rightRotate(root->right); return leftRotate(root); } } return root; }

// Print the tree void printTree(Node *root, string indent, bool last) { if (root != nullptr) { cout << indent; if (last) { cout << "R----"; indent += " "; } else { cout << "L----"; indent += "| "; } cout << root->key << endl; printTree(root->left, indent, false); printTree(root->right, indent, true); } }

int main() { Node *root = NULL; root = insertNode(root, 33); root = insertNode(root, 13); root = insertNode(root, 53); root = insertNode(root, 9); root = insertNode(root, 21); root = insertNode(root, 61); root = insertNode(root, 8); root = insertNode(root, 11); printTree(root, "", true); root = deleteNode(root, 13); cout << "After deleting " << endl; printTree(root, "", true); }

HEIGHT AND DIAMETER OF BINARY TREE

// Simple C++ program to find diameter // of a binary tree.

include <bits/stdc++.h>

using namespace std;

/ Tree node structure used in the program / struct Node { int data; Node left, right; };

/ Function to find height of a tree / int height(Node* root, int& ans) { if (root == NULL) return 0;

int left_height = height(root->left, ans);

int right_height = height(root->right, ans);

// update the answer, because diameter of a
// tree is nothing but maximum value of
// (left_height + right_height + 1) for each node
ans = max(ans, 1 + left_height + right_height);

return 1 + max(left_height, right_height);

}

/ Computes the diameter of binary tree with given root. / int diameter(Node* root) { if (root == NULL) return 0; int ans = INT_MIN; // This will store the final answer height(root, ans); return ans; }

struct Node newNode(int data) { struct Node node = new Node; node->data = data; node->left = node->right = NULL;

return (node);

}

// Driver code int main() { struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5);

printf("Diameter is %d\n", diameter(root));

return 0;

}

FLATTEN BINARY TREE TO LL

// C++ Program to flatten a given Binary Tree into linked // list

include <bits/stdc++.h>

using namespace std;

struct Node { int key; Node left, right; };

// utility that allocates a new Node with the given key Node newNode(int key) { Node node = new Node; node->key = key; node->left = node->right = NULL; return (node); }

// Function to convert binary tree into linked list by // altering the right node and making left node point to // NULL void flatten(struct Node root) { // base condition- return if root is NULL or if it is a // leaf node if (root == NULL || root->left == NULL && root->right == NULL) return; // if root->left exists then we have to make it // root->right if (root->left != NULL) { // move left recursively flatten(root->left); // store the node root->right struct Node tmpRight = root->right; root->right = root->left; root->left = NULL; // find the position to insert the stored value struct Node* t = root->right; while (t->right != NULL) t = t->right; // insert the stored value t->right = tmpRight; } // now call the same function for root->right flatten(root->right); }

// To find the inorder traversal void inorder(struct Node* root) { // base condition if (root == NULL) return; inorder(root->left); cout << root->key << " "; inorder(root->right); }

/ Driver program to test above functions/ int main() { / 1 / \ 2 5 / \ \ 3 4 6 / Node* root = newNode(1); root->left = newNode(2); root->right = newNode(5); root->left->left = newNode(3); root->left->right = newNode(4); root->right->right = newNode(6); flatten(root); cout << "The Inorder traversal after flattening binary tree "; inorder(root); return 0; }

SORTED ARRAY TO BALANCED BST

// C++ program to print BST in given range

include<bits/stdc++.h>

using namespace std;

/ A Binary Tree node / class TNode { public: int data; TNode left; TNode right; };

TNode* newNode(int data);

/ A function that constructs Balanced Binary Search Tree from a sorted array / TNode sortedArrayToBST(int arr[],int start, int end) { / Base Case */ if (start > end) return NULL;

/* Get the middle element and make it root */
int mid = (start + end)/2;
TNode *root = newNode(arr[mid]);

/* Recursively construct the left subtree
and make it left child of root */
root->left = sortedArrayToBST(arr, start,mid - 1);

/* Recursively construct the right subtree
and make it right child of root */
root->right = sortedArrayToBST(arr, mid + 1, end);

return root;

}

/ Helper function that allocates a new node with the given data and NULL left and right pointers. / TNode newNode(int data) { TNode node = new TNode(); node->data = data; node->left = NULL; node->right = NULL;

return node;

}

/ A utility function to print preorder traversal of BST / void preOrder(TNode* node) { if (node == NULL) return; cout << node->data << " "; preOrder(node->left); preOrder(node->right); }

// Driver Code int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]);

/* Convert List to BST */
TNode *root = sortedArrayToBST(arr, 0, n-1);
cout << "PreOrder Traversal of constructed BST \n";
preOrder(root);

return 0;

}

MERGE TWO BST

include<bits/stdc++.h>

using namespace std;

class node { public: int data; node left; node right; };

int *merge(int arr1[], int arr2[], int m, int n);

void storeInorder(node node, int inorder[],int index_ptr);

node* sortedArrayToBST(int arr[], int start, int end);

node mergeTrees(node root1, node *root2, int m, int n) {

int *arr1 = new int[m];
int i = 0;
storeInorder(root1, arr1, &i);


int *arr2 = new int[n];
int j = 0;
storeInorder(root2, arr2, &j);


int *mergedArr = merge(arr1, arr2, m, n);


return sortedArrayToBST (mergedArr, 0, m + n - 1);

}

node newNode(int data) { node Node = new node(); Node->data = data; Node->left = NULL; Node->right = NULL;

return(Node);

}

void printInorder(node* node) { if (node == NULL) return;

printInorder(node->left);

cout << node->data << " ";


printInorder(node->right);

}

int *merge(int arr1[], int arr2[], int m, int n) {

int *mergedArr = new int[m + n];
int i = 0, j = 0, k = 0;


while (i < m && j < n)
{

    if (arr1[i] < arr2[j])
    {
        mergedArr[k] = arr1[i];
        i++;
    }
    else
    {
        mergedArr[k] = arr2[j];
        j++;
    }
    k++;
}

while (i < m)
{
    mergedArr[k] = arr1[i];
    i++; k++;
}


while (j < n)
{
    mergedArr[k] = arr2[j];
    j++; k++;
}

return mergedArr;

}

void storeInorder(node node, int inorder[], int index_ptr) { if (node == NULL) return;

storeInorder(node->left, inorder, index_ptr);

inorder[*index_ptr] = node->data;
(*index_ptr)++;

storeInorder(node->right, inorder, index_ptr);

}

node* sortedArrayToBST(int arr[], int start, int end) {

if (start > end)
return NULL;


int mid = (start + end)/2;
node *root = newNode(arr[mid]);


root->left = sortedArrayToBST(arr, start, mid-1);


root->right = sortedArrayToBST(arr, mid+1, end);

return root;

}

int main() {

node *root1 = newNode(100);
root1->left  = newNode(50);
root1->right = newNode(300);
root1->left->left = newNode(20);
root1->left->right = newNode(70);


node *root2 = newNode(80);
root2->left  = newNode(40);
root2->right = newNode(120);

node *mergedTree = mergeTrees(root1, root2, 5, 3);

cout << "Following is Inorder traversal of the merged tree \n";
printInorder(mergedTree);

return 0;

}

K-th largest element in BST

// C++ program to find k'th largest element in BST

include<bits/stdc++.h>

using namespace std;

struct Node { int key; Node left, right; };

// A utility function to create a new BST node Node newNode(int item) { Node temp = new Node; temp->key = item; temp->left = temp->right = NULL; return temp; }

// A function to find k'th largest element in a given tree. void kthLargestUtil(Node *root, int k, int &c) { // Base cases, the second condition is important to // avoid unnecessary recursive calls if (root == NULL || c >= k) return;

// Follow reverse inorder traversal so that the
// largest element is visited first
kthLargestUtil(root->right, k, c);

// Increment count of visited nodes
c++;

// If c becomes k now, then this is the k'th largest
if (c == k)
{
    cout << "K'th largest element is "
        << root->key << endl;
    return;
}

// Recur for left subtree
kthLargestUtil(root->left, k, c);

}

// Function to find k'th largest element void kthLargest(Node *root, int k) { // Initialize count of nodes visited as 0 int c = 0;

// Note that c is passed by reference
kthLargestUtil(root, k, c);

}

/ A utility function to insert a new node with given key in BST / Node insert(Node node, int key) { / If the tree is empty, return a new node / if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */
if (key < node->key)
    node->left = insert(node->left, key);
else if (key > node->key)
    node->right = insert(node->right, key);

/* return the (unchanged) node pointer */
return node;

}

// Driver Program to test above functions int main() { / Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 / Node *root = NULL; root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80);

int c = 0;
for (int k=1; k<=7; k++)
    kthLargest(root, k);

return 0;

}

MIN ABSOLUTE DIFFERENCE

// C++ implementation of the approach

include <bits/stdc++.h>

using namespace std;

// Node of the binary tree struct node { int data; node left; node right; node(int data) { this->data = data; left = NULL; right = NULL; } };

// Function for in-order traversal of the tree void inorder(node curr, node& prev, int& ans) {

// Base-case
if (curr == NULL)
    return;

// Calling in-order on the left sub-tree
inorder(curr->left, prev, ans);

if (prev != NULL)
    ans = min(curr->data - prev->data, ans);
prev = curr;

// Calling in-order on the right sub-tree
inorder(curr->right, prev, ans);

}

// Function to return the minimum // difference between any two nodes // of the given binary search tree int minDiff(node* root) {

// Pointer to previous node in the
// in-order traversal of the BST
node* prev = NULL;

// To store the final ans
int ans = INT_MAX;

// Call in-order for the BST
inorder(root, prev, ans);

// Returning the final answer
return ans;

}

// Driver code int main() { node* root = new node(5); root->left = new node(3); root->right = new node(7); root->left->left = new node(2); root->left->right = new node(4); root->right->left = new node(6); root->right->right = new node(8);

cout << minDiff(root);

return 0;

}

Sliding window maximum

// C++ program to find the maximum for each // and every contiguous subarray of size K

include <bits/stdc++.h>

using namespace std;

// Function to find the maximum for each // and every contiguous subarray of size k void printKMax(int a[], int n, int k) { // If k = 1, print all elements if (k == 1) { for (int i = 0; i < n; i += 1) cout << a[i] << " "; return; }

// Using p and q as variable pointers
// where p iterates through the subarray
// and q marks end of the subarray.
int p = 0,
    q = k - 1,
    t = p,
    max = a[k - 1];

// Iterating through subarray.
while (q <= n - 1) {

    // Finding max
    // from the subarray.
    if (a[p] > max)
        max = a[p];

    p += 1;

    // Printing max of subarray
    // and shifting pointers
    // to next index.
    if (q == p && p != n) {
        cout << max << " ";
        q++;
        p = ++t;

        if (q < n)
            max = a[q];
    }
}

}

// Driver Code int main() { int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int n = sizeof(a) / sizeof(a[0]); int K = 3;

printKMax(a, n, K);

return 0;

}

MERGE K SORTED LIST

// C++ implementation to merge k // sorted linked lists // | Using MIN HEAP method

include <bits/stdc++.h>

using namespace std;

struct Node { int data; struct Node* next; };

// Utility function to create // a new node struct Node newNode(int data) { // Allocate node struct Node new_node = new Node();

// Put in the data
new_node->data = data;
new_node->next = NULL;

return new_node;

}

// 'compare' function used to build // up the priority queue struct compare { bool operator()( struct Node a, struct Node b) { return a->data > b->data; } };

// Function to merge k sorted linked lists struct Node mergeKSortedLists( struct Node arr[], int k) { // Priority_queue 'pq' implemented // as min heap with the help of // 'compare' function priority_queue<Node, vector<Node>, compare> pq;

// Push the head nodes of all
// the k lists in 'pq'
for (int i = 0; i < k; i++)
    if (arr[i] != NULL)
        pq.push(arr[i]);

// Handles the case when k = 0
// or lists have no elements in them
if (pq.empty())
    return NULL;

struct Node *dummy = newNode(0);
struct Node *last = dummy;

// Loop till 'pq' is not empty
while (!pq.empty())
{
    // Get the top element of 'pq'
    struct Node* curr = pq.top();
    pq.pop();

    // Add the top element of 'pq'
    // to the resultant merged list
    last->next = curr;
    last = last->next;

    // Check if there is a node
    // next to the 'top' node
    // in the list of which 'top'
    // node is a member
    if (curr->next != NULL)

    // Push the next node of top node
    // in 'pq'
    pq.push(curr->next);
}

// Address of head node of the required
// merged list
return dummy->next;

}

// Function to print the singly // linked list void printList(struct Node* head) { while (head != NULL) { cout << head->data << " "; head = head->next; } }

// Driver code int main() { // Number of linked lists int k = 3;

// Number of elements in each list
int n = 4;

// An array of pointers storing the
// head nodes of the linked lists
Node* arr[k];

// Creating k = 3 sorted lists
arr[0] = newNode(1);
arr[0]->next = newNode(3);
arr[0]->next->next = newNode(5);
arr[0]->next->next->next = newNode(7);

arr[1] = newNode(2);
arr[1]->next = newNode(4);
arr[1]->next->next = newNode(6);
arr[1]->next->next->next = newNode(8);

arr[2] = newNode(0);
arr[2]->next = newNode(9);
arr[2]->next->next = newNode(10);
arr[2]->next->next->next = newNode(11);

// Merge the k sorted lists
struct Node* head = mergeKSortedLists(arr, k);

// Print the merged list
printList(head);

return 0;

}

MIN HEAP TO MAX HEAP

// A C++ program to convert min Heap to max Heap

include<bits/stdc++.h>

using namespace std;

// to heapify a subtree with root at given index void MaxHeapify(int arr[], int i, int n) { int l = 2i + 1; int r = 2i + 2; int largest = i; if (l < n && arr[l] > arr[i]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { swap(arr[i], arr[largest]); MaxHeapify(arr, largest, n); } }

// This function basically builds max heap void convertMaxHeap(int arr[], int n) { // Start from bottommost and rightmost // internal mode and heapify all internal // modes in bottom up way for (int i = (n-2)/2; i >= 0; --i) MaxHeapify(arr, i, n); }

// A utility function to print a given array // of given size void printArray(int* arr, int size) { for (int i = 0; i < size; ++i) printf("%d ", arr[i]); }

// Driver program to test above functions int main() { // array representing Min Heap int arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9}; int n = sizeof(arr)/sizeof(arr[0]);

printf("Min Heap array : ");
printArray(arr, n);

convertMaxHeap(arr, n);

printf("\nMax Heap array : ");
printArray(arr, n);

return 0;

}

HEAP DATA STRUCTURE

// Max-Heap data structure in C++

include <iostream>

include <vector>

using namespace std;

void swap(int a, int b) { int temp = b; b = a; a = temp; } void heapify(vector<int> &hT, int i) { int size = hT.size(); int largest = i; int l = 2 i + 1; int r = 2 i + 2; if (l < size && hT[l] > hT[largest]) largest = l; if (r < size && hT[r] > hT[largest]) largest = r;

if (largest != i) { swap(&hT[i], &hT[largest]); heapify(hT, largest); } } void insert(vector<int> &hT, int newNum) { int size = hT.size(); if (size == 0) { hT.push_back(newNum); } else { hT.push_back(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(vector<int> &hT, int num) { int size = hT.size(); int i; for (i = 0; i < size; i++) { if (num == hT[i]) break; } swap(&hT[i], &hT[size - 1]);

hT.pop_back(); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } void printArray(vector<int> &hT) { for (int i = 0; i < hT.size(); ++i) cout << hT[i] << " "; cout << "\n"; }

int main() { vector<int> heapTree;

insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2);

cout << "Max-Heap array: "; printArray(heapTree);

deleteNode(heapTree, 4);

cout << "After deleting an element: ";

printArray(heapTree); }