Roll no :42

Practical no
Radix Sort

Q. Write a Program to implement Radix Sort.

#include <iostream>

using namespace std;

int getMax(int arr[], int n)

{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}

void countSort(int arr[], int n, int exp)

{

int output[n], i, count[10] = {0};

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

count[(arr[i] / exp) % 10]++;

for (i = 1; i < 10; i++)

count[i] += count[i-1];

for (i = n - 1; i >= 0; i--)

{
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}

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

arr[i] = output[i];
}
void radixsort(int arr[], int n)
{
int exp, m;
m = getMax(arr, n);
for (exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
 Roll no :42

int main()
{
cout<<"\n Roll no:42\n";
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;

int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}

radixsort(arr, n);
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}

Output:
 Roll no :42

Practical no
Min Heap

Q. Write a Program to implement Min Heap.

#include <iostream>

using namespace std;

void min_heapify(int *a,int i,int n)
{
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= n)
{
if (j < n && a[j+1] < a[j])
j = j + 1;
if (temp < a[j])
break;
else if (temp >= a[j])
{
a[j/2] = a[j];
j = 2 * j;
}
}
a[j/2] = temp;
return;
}
void build_minheap(int *a, int n)
{
int i;
for(i = n/2; i >= 1; i--)
{
min_heapify(a,i,n);
}
}
int main()
{
cout<<"\n Roll no:42\n";
int n, i, x;
cout<<"Min Heap\n";
cout<<"enter no of elements of array\n";
cin>>n;
int a[20];
for (i = 1; i <= n; i++)
{
 Roll no :42

cout<<"enter element"<<(i)<<endl;
cin>>a[i];
}
build_minheap(a, n);
cout<<"Min Heap\n";
for (i = 1; i <= n; i++)
{
cout<<a[i]<<endl;
}
}

Output:
 Roll no :42

Practical no
Max Heap

Q. Write a Program to implement Max Heap.

#include <iostream>

using namespace std;

void MaxHeapify(int a[], int i, int n)

{
int j, temp;
temp = a[i];
j = 2*i;

while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j+1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void HeapSort(int a[], int n)
{
int i, temp;
for (i = n; i >= 2; i--)
{
temp = a[i];
a[i] = a[1];
a[1] = temp;
MaxHeapify(a, 1, i - 1);
}
}
void Build_MaxHeap(int a[], int n)
{
int i;
for(i = n/2; i >= 1; i--)
MaxHeapify(a, i, n);
 Roll no :42

}
int main()
{
cout<<"\nRoll no:42\n";
int n, i;
cout<<"Heap Sort\n";
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
n++;
int arr[n];
for(i = 1; i < n; i++)
{
cout<<"Enter element "<<i<<": ";
cin>>arr[i];
}
Build_MaxHeap(arr, n-1);
HeapSort(arr, n-1);

cout<<"\nSorted Data ";

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

cout<<"->"<<arr[i];

return 0;
}

Output:
 Roll no :42

Practical no
Binary Heap

Q. Write a Program to implement Binary Heap.

#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;

class BinaryHeap
{
private:
vector <int> heap;
int left(int parent);
int right(int parent);
int parent(int child);
void heapifyup(int index);
void heapifydown(int index);
public:
BinaryHeap()
{}
void Insert(int element);
void DeleteMin();
int ExtractMin();
void DisplayHeap();
int Size();
};
int BinaryHeap::Size()
{
return heap.size();
}

void BinaryHeap::Insert(int element)

{
heap.push_back(element);
heapifyup(heap.size() -1);
}

void BinaryHeap::DeleteMin()
{
if (heap.size() == 0)
{
cout<<"Heap is Empty"<<endl;
return;
 Roll no :42

}
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
cout<<"Element Deleted"<<endl;
}

int BinaryHeap::ExtractMin()
{
if (heap.size() == 0)
{
return -1;
}
else
return heap.front();
}

void BinaryHeap::DisplayHeap()
{
vector <int>::iterator pos = heap.begin();
cout<<"Heap --> ";
while (pos != heap.end())
{
cout<<*pos<<" ";
pos++;
}
cout<<endl;
}

int BinaryHeap::left(int parent)

{
int l = 2 * parent + 1;
if (l < heap.size())
return l;
else
return -1;
}

int BinaryHeap::right(int parent)

{
int r = 2 * parent + 2;
if (r < heap.size())
return r;
else
return -1;
}
 Roll no :42

int BinaryHeap::parent(int child)

{
int p = (child - 1)/2;
if (child == 0)
return -1;
else
return p;
}

void BinaryHeap::heapifyup(int in)

{
if (in >= 0 && parent(in) >= 0 && heap[parent(in)] > heap[in])
{
int temp = heap[in];
heap[in] = heap[parent(in)];
heap[parent(in)] = temp;
heapifyup(parent(in));
}
}

void BinaryHeap::heapifydown(int in)

{
int child = left(in);
int child1 = right(in);
if (child >= 0 && child1 >= 0 && heap[child] > heap[child1])
{
child = child1;
}
if (child > 0 && heap[in] > heap[child])
{
int temp = heap[in];
heap[in] = heap[child];
heap[child] = temp;
heapifydown(child);
}
}

int main()
{
cout<<"\nRoll no:42\n";
BinaryHeap h;

cout<<"Binary Heap"<<endl;
cout<<"1.Insert Element"<<endl;
cout<<"2.Delete Minimum Element"<<endl;
 Roll no :42

cout<<"3.Extract Minimum Element"<<endl;

cout<<"4.Print Heap"<<endl;
cout<<"5.Exit"<<endl;
int choice, element;
while (1)
{
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the element to be inserted: ";
cin>>element;
h.Insert(element);
break;
case 2:
h.DeleteMin();
break;
case 3:
cout<<"Minimum Element: ";
if (h.ExtractMin() == -1)
{
cout<<"Heap is Empty"<<endl;
}
else
cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
break;
case 4:
cout<<"Displaying elements of Heap: ";
h.DisplayHeap();
break;
case 5:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
}
}
return 0;
}
 Roll no :42

Output:
 Roll no :42

Practical no
Breadth First Search

Q. Write a Program to implement Breadth First Search.

#include<iostream>
#include <list>

using namespace std;

class Graph
{
int V;

list<int> *adj;
public:
Graph(int V);

void addEdge(int v, int w);

void BFS(int s);

};

Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)

{
adj[v].push_back(w);
}

void Graph::BFS(int s)
{
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;

list<int> queue;

visited[s] = true;
queue.push_back(s);

list<int>::iterator i;
 Roll no :42

while(!queue.empty())
{
s = queue.front();
cout << s << " ";
queue.pop_front();

for (i = adj[s].begin(); i != adj[s].end(); ++i)

{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}

int main()
{
Cout<<Roll no:42/n
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.addEdge(4,3);

cout << "Following is Breadth First Traversal\n";

g.BFS(2);

return 0;
}
 Roll no :42

Output: