red black tree
LEFT ROTATE (T, x)
1. y ← right [x]
1. y ← right [x]
2. right [x] ← left [y]
3. p [left[y]] ← x
4. p[y] ← p[x]
5. If p[x] = nil [T]
then root [T] ← y
else if x = left [p[x]]
then left [p[x]] ← y
else right [p[x]] ← y
6. left [y] ← x.
7. p [x] ← y.
RB-INSERT (T, z)
1. y ← nil [T]
2. x ← root [T]
3. while x ≠ NIL [T]
4. do y ← x
5. if key [z] < key [x]
6. then x ← left [x]
7. else x ← right [x]
8. p [z] ← y
9. if y = nil [T]
10. then root [T] ← z
11. else if key [z] < key [y]
12. then left [y] ← z
13. else right [y] ← z
14. left [z] ← nil [T]
15. right [z] ← nil [T]
16. color [z] ← RED
17. RB-INSERT-FIXUP (T, z)
RB-DELETE (T, z)
1. if left [z] = nil [T] or right [z] = nil [T]
2. then y ← z
3. else y ← TREE-SUCCESSOR (z)
4. if left [y] ≠ nil [T]
5. then x ← left [y]
6. else x ← right [y]
7. p [x] ← p [y]
8. if p[y] = nil [T]
9. then root [T] ← x
10. else if y = left [p[y]]
11. then left [p[y]] ← x
12. else right [p[y]] ← x
13. if y≠ z
14. then key [z] ← key [y]
15. copy y's satellite data into z
16. if color [y] = BLACK
17. then RB-delete-FIXUP (T, x)
18. return y
avl tree
function balance(current)
if current == NULL then \\Nothing to balance
return current
end if
computeHeightFromChildren(current) \\update current’s height
lef tH = current→lef t→height
rightH = current→right→height
if lef tH > rightH 1 then \\Left subtree is too tall
lef tlef tH = current→lef t→lef t→height
lef trightH = current→lef t→right→height
if lef tlef tH >= lef trightH then
return rightRotate(current) \\left-outer grandchild is taller
else
return leftRightRotate(current) \\left-inner grandchild is taller
end if
end if
if rightH > lef tH 1 then \\Right subtree is too tall
rightlef tH = current→right→lef t→height
rightrightH = current→right→right→height
if rightrightH >= rightlef tH then
return leftRotate(current) \\right-outer grandchild is taller
else
return rightLeftRotate(current) \\right-inner grandchild is taller
end if
end if
return current \\No rotation, so root is the same
end function
function rightRotate(current)
newRoot = current → lef t
current → lef t = newRoot → right
newRoot → right = current
computeHeightF romChildren(current)
computeHeightF romChildren(newRoot)
return newRoot
end function
function leftRightRotate(current)
current → lef t = lef tRotate(current → lef t)
return rightRotate(current)
end function
function computeHeightFromChildren(current)
lef tH = current → lef t → height
rightH = current → right → height
height = 1 max(lef tH, rightH)
end function
Skip list
// C++ code for searching and deleting element in skip list
#include <bits/stdc++.h>
using namespace std;
// Class to implement node
class Node
{
public:
int key;
// Array to hold pointers to node of different level
Node **forward;
Node(int, int);
};
Node::Node(int key, int level)
{
this->key = key;
// Allocate memory to forward
forward = new Node*[level+1];
// Fill forward array with 0(NULL)
memset(forward, 0, sizeof(Node*)*(level+1));
};
// Class for Skip list
class SkipList
{
// Maximum level for this skip list
int MAXLVL;
// P is the fraction of the nodes with level
// i pointers also having level i+1 pointers
float P;
// current level of skip list
int level;
// pointer to header node
Node *header;
public:
SkipList(int, float);
int randomLevel();
Node* createNode(int, int);
void insertElement(int);
void deleteElement(int);
void searchElement(int);
void displayList();
};
SkipList::SkipList(int MAXLVL, float P)
{
this->MAXLVL = MAXLVL;
this->P = P;
level = 0;
// create header node and initialize key to -1
header = new Node(-1, MAXLVL);
};
// create random level for node
int SkipList::randomLevel()
{
float r = (float)rand()/RAND_MAX;
int lvl = 0;
while(r < P && lvl < MAXLVL)
{
lvl++;
r = (float)rand()/RAND_MAX;
}
return lvl;
};
// create new node
Node* SkipList::createNode(int key, int level)
{
Node *n = new Node(key, level);
return n;
};
// Insert given key in skip list
void SkipList::insertElement(int key)
{
Node *current = header;
// create update array and initialize it
Node *update[MAXLVL+1];
memset(update, 0, sizeof(Node*)*(MAXLVL+1));
/* start from highest level of skip list
move the current pointer forward while key
is greater than key of node next to current
Otherwise inserted current in update and
move one level down and continue search
*/
for(int i = level; i >= 0; i--)
{
while(current->forward[i] != NULL &&
current->forward[i]->key < key)
current = current->forward[i];
update[i] = current;
}
/* reached level 0 and forward pointer to
right, which is desired position to
insert key.
*/
current = current->forward[0];
/* if current is NULL that means we have reached
to end of the level or current's key is not equal
to key to insert that means we have to insert
node between update[0] and current node */
if (current == NULL || current->key != key)
{
// Generate a random level for node
int rlevel = randomLevel();
/* If random level is greater than list's current
level (node with highest level inserted in
list so far), initialize update value with pointer
to header for further use */
if(rlevel > level)
{
for(int i=level+1;i<rlevel+1;i++)
update[i] = header;
// Update the list current level
level = rlevel;
}
// create new node with random level generated
Node* n = createNode(key, rlevel);
// insert node by rearranging pointers
for(int i=0;i<=rlevel;i++)
{
n->forward[i] = update[i]->forward[i];
update[i]->forward[i] = n;
}
cout<<"Successfully Inserted key "<<key<<"\n";
}
};
// Delete element from skip list
void SkipList::deleteElement(int key)
{
Node *current = header;
// create update array and initialize it
Node *update[MAXLVL+1];
memset(update, 0, sizeof(Node*)*(MAXLVL+1));
/* start from highest level of skip list
move the current pointer forward while key
is greater than key of node next to current
Otherwise inserted current in update and
move one level down and continue search
*/
for(int i = level; i >= 0; i--)
{
while(current->forward[i] != NULL &&
current->forward[i]->key < key)
current = current->forward[i];
update[i] = current;
}
/* reached level 0 and forward pointer to
right, which is possibly our desired node.*/
current = current->forward[0];
// If current node is target node
if(current != NULL and current->key == key)
{
/* start from lowest level and rearrange
pointers just like we do in singly linked list
to remove target node */
for(int i=0;i<=level;i++)
{
/* If at level i, next node is not target
node, break the loop, no need to move
further level */
if(update[i]->forward[i] != current)
break;
update[i]->forward[i] = current->forward[i];
}
// Remove levels having no elements
while(level>0 &&
header->forward[level] == 0)
level--;
cout<<"Successfully deleted key "<<key<<"\n";
}
};
void SkipList::searchElement(int key)
{
Node *current = header;
for(int i = level; i >= 0; i--)
{
while(current->forward[i] &&
current->forward[i]->key < key)
current = current->forward[i];
}
current = current->forward[0];
if(current and current->key == key)
cout<<"Found key: "<<key<<"\n";
};
// Display skip list level wise
void SkipList::displayList()
{
cout<<"\n*****Skip List*****"<<"\n";
for(int i=0;i<=level;i++)
{
Node *node = header->forward[i];
cout<<"Level "<<i<<": ";
while(node != NULL)
{
cout<<node->key<<" ";
node = node->forward[i];
}
cout<<"\n";
}
};
// Driver to test above code
int main()
{
// Seed random number generator
srand((unsigned)time(0));
// create SkipList object with MAXLVL and P
SkipList lst(3, 0.5);
lst.insertElement(3);
lst.insertElement(6);
lst.insertElement(7);
lst.insertElement(9);
lst.insertElement(12);
lst.insertElement(19);
lst.insertElement(17);
lst.insertElement(26);
lst.insertElement(21);
lst.insertElement(25);
lst.displayList();
//Search for node 19
lst.searchElement(19);
//Delete node 19
lst.deleteElement(19);
lst.displayList();
}
XOR inked list
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
// Data structure to store a XOR linked list node
struct Node
{
int data;
struct Node* link;
};
// Helper function to return XOR of `x` and `y`
struct Node* XOR(struct Node *x, struct Node *y) {
return (struct Node*)((uintptr_t)(x) ^ (uintptr_t)(y));
}
// Helper function to traverse the list in a forward direction
void traverse(struct Node *head)
{
struct Node* curr = head;
struct Node* prev = NULL;
struct Node *next;
while (curr != NULL)
{
printf("%d —> ", curr->data);
// `next` node would be xor of the address of the previous node
// and current node link
next = XOR(prev, curr->link);
// update `prev` and `curr` pointers for the next iteration of the loop
prev = curr;
curr = next;
}
printf("NULL");
}
// Helper function to insert a node at the beginning of the XOR linked list
void push(struct Node **head, int data)
{
// allocate a new list node and set its data
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
// The link field of the new node is XOR of the current head and `NULL`
// since a new node is being inserted at the beginning
newNode->link = XOR(*head, NULL);
// update link value of the current head node if the linked list is not empty
if (*head)
{
// *(head)->link is XOR of `NULL` and address of the next node.
// To get the address of the next node, XOR it with `NULL`
(*head)->link = XOR(newNode, XOR((*head)->link, NULL));
}
// update the head pointer
*head = newNode;
}
int main(void)
{
// input keys
int keys[] = { 1, 2, 3, 4, 5 };
int n = sizeof(keys)/sizeof(keys[0]);
struct Node* head = NULL;
for (int i = n - 1; i >=0; i--) {
push(&head, keys[i]);
}
traverse(head);
return 0;
}
Output:
1 —> 2 —> 3 —> 4 —> 5 —> NULL
BTREE
#include<iostream>
using namespace std;
class BTreeNode
{
int *keys;
int t;
BTreeNode **C;
int n;
bool leaf;
public:
BTreeNode(int _t, bool _leaf);
void insertNonFull(int k);
void splitChild(int i, BTreeNode *y);
void traverse();
friend class BTree;
};
class BTree
{
BTreeNode *root;
int t;
public:
BTree(int _t)
{ root = NULL; t = _t; }
void traverse()
{ if (root != NULL) root->traverse(); }
void insert(int k);
};
BTreeNode::BTreeNode(int t1, bool leaf1)
{
t = t1;
leaf = leaf1;
keys = new int[2*t-1];
C = new BTreeNode *[2*t];
n = 0;
}
void BTreeNode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
void BTree::insert(int k)
{
if (root == NULL)
{
root = new BTreeNode(t, true);
root->keys[0] = k;
root->n = 1;
}
else
{
if (root->n == 2*t-1)
{
BTreeNode *s = new BTreeNode(t, false);
s->C[0] = root;
s->splitChild(0, root);
int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);
root = s;
}
else
root->insertNonFull(k);
}
}
void BTreeNode::insertNonFull(int k)
{
int i = n-1;
if (leaf == true)
{
while (i >= 0 && keys[i] > k)
{
keys[i+1] = keys[i];
i--;
}
keys[i+1] = k;
n = n+1;
}
else
{
while (i >= 0 && keys[i] > k)
i--;
if (C[i+1]->n == 2*t-1)
{
splitChild(i+1, C[i+1]);
if (keys[i+1] < k)
i++;
}
C[i+1]->insertNonFull(k);
}
}
void BTreeNode::splitChild(int i, BTreeNode *y)
{
BTreeNode *z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t-1; j++)
z->keys[j] = y->keys[j+t];
if (y->leaf == false)
{
for (int j = 0; j < t; j++)
z->C[j] = y->C[j+t];
}
y->n = t - 1;
for (int j = n; j >= i+1; j--)
C[j+1] = C[j];
C[i+1] = z;
for (int j = n-1; j >= i; j--)
keys[j+1] = keys[j];
keys[i] = y->keys[t-1];
n = n + 1;
}
int main()
{
int degree,n,num;
cout<<"Enter degree"<<endl;
cin>>degree;
BTree t(degree);
cout<<"Enter no of elements"<<endl;
cin>>n;
cout<<"Enter elements"<<endl;
for(int i=0;i<n;i++)
{
cin>>num;
t.insert(num);
}
cout << "Traversal of the constucted tree is ";
t.traverse();
return 0;
}
Island counter
#include<bits/stdc++.h>
using namespace std;
class DisjointUnionSets
{
public:
vector<int> rank, parent;
int n;
DisjointUnionSets(int n);
void makeSet();
int find(int x);
void Union(int x, int y);
};
DisjointUnionSets::DisjointUnionSets(int n)
{
rank.resize(n);
parent.resize(n);
this->n = n;
makeSet();
}
void DisjointUnionSets::makeSet()
{
for(int i=0; i<n; i++)
{
parent[i] = i;
rank[i] = 0;
}
}
int DisjointUnionSets:: find(int x)
{
if(parent[x] == x)
return x;
else
return find(parent[x]);
}
void DisjointUnionSets::Union(int x, int y)
{
int xRoot = find(x);
int yRoot = find(y);
if(xRoot == yRoot)
return;
if( rank[xRoot] > rank[yRoot])
parent[yRoot] = xRoot;
else if (rank[yRoot] > rank[xRoot])
parent[xRoot] = yRoot;
else
{
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
int countIslands(vector<vector<int>>a)
{
int n = a.size();
int m = a[0].size();
DisjointUnionSets *obj = new DisjointUnionSets(n*m);
for(int j=0; j<n; j++)
{
for(int k=0; k<n; k++)
{
if(a[j][k] == 0)
continue;
if(j+1 < n && a[j+1][k] == 1)
obj->Union(j*m + k, (j+1)*m + k);
if(j-1 >= 0 && a[j-1][k] == 1)
obj->Union(j*m + k, (j-1)*m + k);
if(k+1 < m && a[j][k+1] == 1)
obj->Union(j*m + k, j*m + k+1);
if(k-1 >= 0 && a[j][k-1] == 1)
obj->Union(j*m + k, j*m + k-1);
if(j-1 >= 0 && k+1 < m && a[j-1][k+1] == 1)
obj->Union(j*m + k, (j-1)*m + k+1);
if(j+1 < n && k+1 < m && a[j+1][k+1] == 1)
obj->Union(j*m + k, (j+1)*m + k+1);
if(j-1 >= 0 && k-1 >= 0 && a[j-1][k-1] == 1)
obj->Union(j*m + k, (j-1)*m + k-1);
if(j+1 < n && k-1 >= 0 && a[j+1][k-1] == 1)
obj->Union(j*m + k, (j+1)*m + k-1);
}
}
int numberOfIslands = 0;
int *c = new int[n*m];
for(int i=0; i<n*m; i++)
{
c[i] = 0;
}
for(int j=0; j<n; j++)
{
for(int k=0; k<m; k++)
{
if(a[j][k] == 1)
{
int x = obj->find(j*m + k);
if(c[x] == 0)
{
c[x]++;
numberOfIslands++;
}
else
c[x]++;
}
}
}
return numberOfIslands;
}
int main()
{
vector<vector<int>>a ={{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}};
cout<<"Number of islands = "<<countIslands(a)<<endl;
return 0;
}
Binomial tree
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
struct Node {
int data, degree;
Node *child, *sibling, *parent;
};
Node* newNode(int key) {
Node *temp = new Node;
temp -> data = key;
temp -> degree = 0;
temp -> child = temp -> parent = temp -> sibling = NULL;
return temp;
}
Node* mergeBinomialTrees(Node *b1, Node *b2) {
if (b1 -> data > b2 -> data) swap(b1, b2);
b2 -> parent = b1;
b2 -> sibling = b1 -> child;
b1 -> child = b2;
b1 -> degree++;
return b1;
}
list<Node*> unionBionomialHeap(list<Node*> l1, list<Node*> l2) {
list<Node*> _new;
list<Node*>::iterator it = l1.begin();
list<Node*>::iterator ot = l2.begin();
while (it != l1.end() && ot != l2.end()) {
if((*it) -> degree <= (*ot) -> degree) {
_new.push_back(*it);
it++;
} else {
_new.push_back(*ot);
ot++;
}
}
while (it != l1.end()) {
_new.push_back(*it);
it++;
}
while (ot != l2.end()) {
_new.push_back(*ot);
ot++;
}
return _new;
}
list<Node*> adjust(list<Node*> _heap) {
if (_heap.size() <= 1) return _heap;
list<Node*> new_heap;
list<Node*>::iterator it1,it2,it3;
it1 = it2 = it3 = _heap.begin();
if (_heap.size() == 2) {
it2 = it1;
it2++;
it3 = _heap.end();
} else {
it2++;
it3 = it2;
it3++;
}
while (it1 != _heap.end()) {
if (it2 == _heap.end()) it1++;
else if ((*it1) -> degree < (*it2) -> degree) {
it1++;
it2++;
if(it3 != _heap.end()) it3++;
}
else if (it3 != _heap.end() && (*it1) -> degree == (*it2) -> degree && (*it1) -> degree == (*it3) -> degree) {
it1++;
it2++;
it3++;
}
else if ((*it1) -> degree == (*it2) -> degree) {
Node *temp;
*it1 = mergeBinomialTrees(*it1,*it2);
it2 = _heap.erase(it2);
if(it3 != _heap.end()) it3++;
}
}
return _heap;
}
list<Node*> insertATreeInHeap(list<Node*> _heap, Node *tree) {
list<Node*> temp;
temp.push_back(tree);
temp = unionBionomialHeap(_heap,temp);
return adjust(temp);
}
list<Node*> removeMinFromTreeReturnBHeap(Node *tree) {
list<Node*> heap;
Node *temp = tree -> child;
Node *lo;
while (temp) {
lo = temp;
temp = temp -> sibling;
lo -> sibling = NULL;
heap.push_front(lo);
}
return heap;
}
list<Node*> insert(list<Node*> _head, int key) {
Node *temp = newNode(key);
return insertATreeInHeap(_head,temp);
}
Node* getMin(list<Node*> _heap) {
list<Node*>::iterator it = _heap.begin();
Node *temp = *it;
while (it != _heap.end()) {
if ((*it) -> data < temp -> data) temp = *it;
it++;
}
return temp;
}
list<Node*> extractMin(list<Node*> _heap) {
list<Node*> new_heap,lo;
Node *temp;
temp = getMin(_heap);
list<Node*>::iterator it;
it = _heap.begin();
while (it != _heap.end()) {
if (*it != temp) new_heap.push_back(*it);
it++;
}
lo = removeMinFromTreeReturnBHeap(temp);
new_heap = unionBionomialHeap(new_heap,lo);
new_heap = adjust(new_heap);
return new_heap;
}
void printTree(Node *h) {
while (h) {
cout << h -> data << " ";
printTree(h -> child);
h = h -> sibling;
}
}
void printHeap(list<Node*> _heap) {
list<Node*> ::iterator it;
it = _heap.begin();
while (it != _heap.end()) {
printTree(*it);
it++;
}
}
int main() {
int ch,key;
list<Node*> _heap;
int n;
cin >> n;
while(n--) {
int k;
cin >> k;
_heap = insert(_heap, k);
}
cout << "Heap elements after insertion:\n";
printHeap(_heap);
Node *temp = getMin(_heap);
cout << "\nMinimum element of heap " << temp -> data << "\n";
_heap = extractMin(_heap);
cout << "Heap after deletion of minimum element\n";
printHeap(_heap);
return 0;
}
Binomial tree heap
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data, degree;
Node *child, *sibling, *parent;
};
Node* newNode(int key) {
Node *temp = new Node;
temp->data = key;
temp->degree = 0;
temp->child = temp->parent = temp->sibling = NULL;
return temp;
}
Node* mergeBinomialTrees(Node* b1,Node* b2){
if(b1->data > b2->data){
swap(b1,b2);
}
b2->parent=b1;
b2->sibling=b1->child;
b1->child=b2;
b1->degree++;
return b1;
}
list<Node*> unionBinomialHeap(list<Node*> h1, list<Node*> h2){
list<Node*> _new;
list<Node*>::iterator it=h1.begin();
list<Node*>::iterator ot=h2.begin();
while(it!=h1.end() && ot!=h2.end()){
if((*it)->degree<=(*ot)->degree){
_new.push_back(*it);
it++;
}
else
{
_new.push_back(*ot);
ot++;
}
}
while(it!=h1.end()){
_new.push_back(*it);
it++;
}
while(ot!=h2.end()){
_new.push_back(*ot);
ot++;
}
return _new;
}
list<Node*> adjust(list<Node*> heap){
if(heap.size()<=1){
return heap;
}
list<Node*>::iterator it1,it2,it3;
it1=it2=it3=heap.begin();
if(heap.size()==2){
it2=it1++;
it2=it3;
}
else{
it2++;
it3=it2++;
}
while(it1!=heap.end()){
if(it2 == heap.end()){
it1++;
}
else if((*it1)->degree<(*it2)->degree)
{
it1++;
it2++;
if(it3!=heap.end())
it3++;
}
else if(it3!=heap.end() and ((*it1)->degree==(*it2)->degree) and (*it1)->degree==(*it3)->degree){
it1++;
it2++;
it3++;
}
else if((*it1)->degree==(*it2)->degree){
Node* temp;
*it1=mergeBinomialTrees(*it1,*it2);
it2=heap.erase(it2);
if(it3 != heap.end())
it3++;
}
}
return heap;
}
list<Node*> insertaTreeInHeap(Node *tree, list<Node*> heap){
list<Node*> temp;
temp.push_back(tree);
temp=unionBinomialHeap(heap,temp);
return adjust(temp);
}
list<Node*> insert(list<Node*> heap,int key){
Node* nod=newNode(key);
heap=insertaTreeInHeap(nod,heap);
return heap;
}
list<Node*> removeMinfromTreeBHeap(Node* tree){
list<Node*> heap;
Node* temp=tree->child;
Node *lo;
while(temp){
lo=temp;
temp=temp->sibling;
lo->sibling=NULL;
heap.push_front(lo);
}
return heap;
}
Node* getMin(list<Node*> heap){
Node* temp;
list<Node*>:: iterator it=heap.begin();
temp=*it;
while(it!= heap.end()){
if((*it)->data<temp->data)
temp=*it;
it++;
}
return temp;
}
list<Node*> extractMin(list<Node*> heap){
list<Node*> new_heap,lo;
Node *temp=getMin(heap);
list<Node*>::iterator it=heap.begin();
while(it!=heap.end()){
if(*it!=temp){
new_heap.push_back(*it);
}
it++;
}
lo=removeMinfromTreeBHeap(temp);
new_heap=unionBinomialHeap(lo,new_heap);
return adjust(new_heap);
}
void printTree(Node* h){
while(h){
cout<<h->data<<" ";
printTree(h->child);
h=h->sibling;
}
}
void printHeap(list<Node*> heap){
list<Node*> :: iterator it=heap.begin();
it=heap.begin();
while(it!=heap.end()){
printTree(*it);
it++;
}
}
Node* findNodeinTree(Node* h,int val){
if(h==NULL)
return NULL;
// cout<<endl<<"value"<<h->data<<endl;
if (h->data == val){
// cout<<"hi";
return h;
}
Node *res = findNodeinTree(h->child,val);
if(res!=NULL)
return res;
return findNodeinTree(h->sibling,val);
}
Node* findNodeinHeap(list<Node*> heap,int val){
list<Node*>::iterator it=heap.begin();
while(it!=heap.end()){
Node* node=findNodeinTree(*it,val);
// printTree(*it);
// cout<<endl;
if(node !=NULL)
return node;
it++;
}
return NULL;
}
void decreaseKeyBHeap(list<Node*>H,int old_val,int new_val)
{
Node* node= findNodeinHeap(H, old_val);
if(node==NULL)
return;
node->data=new_val;
Node *parent = node->parent;
while(parent!=NULL && parent->data>node->data){
swap(node->data,parent->data);
node=parent;
parent=parent->parent;
}
}
list<Node*> DeleteNodefromHeap(list<Node*> heap,int val){
decreaseKeyBHeap(heap,val,INT_MIN);
return extractMin(heap);
}
int main()
{
int ch,key;
list<Node*> heap;
heap=insert (heap,10);
heap=insert (heap,20);
heap=insert (heap,30);
heap=insert (heap,40);
heap=insert (heap,50);
heap=insert (heap,60);
cout<<"The Elements of the heap after insertion are"<<endl;
printHeap(heap);
Node* temp=getMin(heap);
cout << "\nMinimum element of heap "<< temp->data << "\n";
heap=extractMin(heap);
cout << "Heap after deletion of minimum element\n";
printHeap(heap);
heap=DeleteNodefromHeap(heap,30);
cout<< "\nHeap after deleting element 30:"<<endl;
printHeap(heap);
cout<<endl;
return 0;
}
Write something awesome.
A rich text editor for writing,
collaborating and sharing