Name :Bhukya Bhanuteja Roll no:12012100
Implementation of priority queue
#include <stdio.h>
int size = 0;
void swap(int *a, int *b) {
int temp = *b;
*b = *a;
*a = temp;
// Function to heapify the tree
void heapify(int array[], int size, int i) {
if (size == 1) {
printf("Single element in the heap");
} else {
// Find the largest among root, left child and right child
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && array[l] > array[largest])
largest = l;
if (r < size && array[r] > array[largest])
largest = r;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&array[i], &array[largest]);
heapify(array, size, largest);
// Function to insert an element into the tree
void insert(int array[], int newNum) {
if (size == 0) {
array[0] = newNum;
size += 1;
} else {
array[size] = newNum;
size += 1;
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(array, size, i);
// Function to delete an element from the tree
void deleteRoot(int array[], int num) {
int i;
for (i = 0; i < size; i++) {
if (num == array[i])
break;
swap(&array[i], &array[size - 1]);
size -= 1;
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(array, size, i);
}
// Print the array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i)
printf("%d ", array[i]);
printf("\n");
// Driver code
int main() {
int array[10];
insert(array, 3);
insert(array, 4);
insert(array, 9);
insert(array, 5);
insert(array, 2);
printf("Max-Heap array: ");
printArray(array, size);
deleteRoot(array, 4);
printf("After deleting an element : " );
printArray(array, size);
Output:
Implementation of Heap sort..
#include <stdio.h>
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void heapify(int arr[], int n, int i) {
int max = i; //Initialize max as root
int leftChild = 2 * i ;
int rightChild = 2 * i + 1;
//If left child is greater than root
if (leftChild < n && arr[leftChild] > arr[max])
max = leftChild;
//If right child is greater than max
if (rightChild < n && arr[rightChild] > arr[max])
max = rightChild;
//If max is not root
if (max != i) {
swap(&arr[i], &arr[max]);
//heapify the affected sub-tree recursively
heapify(arr, n, max);
}
}
//Main function to perform heap sort
void heapSort(int arr[], int n) {
//Rearrange array (building heap)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
//Extract elements from heap one by one
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]); //Current root moved to the end
heapify(arr, i, 0); //calling max heapify on the heap reduced
}
}
//print size of array n using utility function
void display(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
//main fucntion
int main() {
int arr[10],j;
int n = sizeof(arr) / sizeof(arr[0]);
printf("Enter the number of element : ");//for user input
scanf("%d",&n);
printf("Enter the elements of array : \n");
for(j=0;j<=n;j++){
scanf("%d",&arr[j]);
}
printf("Original array:\n");
display(arr, n);
heapSort(arr, n);
printf("Sorted array:\n");
display(arr, n);
}
Implementation of bfs:
#include <stdio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v);
main()
{
int v;
printf("enter the number of vertices: ");
scanf("%d",&n);
printf("enter the adjacency matrix: ");
for(i=0;i<n;i++)
{
for(j=0; j<n; j++)
scanf("%d",&a[i][j]);
}
printf("enter the starting vertex:");
scanf("%d" ,&v);
for(i=0;i<n;i++){
q[i]=0;
visited[i]=0;
}
bfs(v);
printf("the rechable nodes are :");
for(i=0;i<n; i++)
{
if (visited[i])
printf("%d\t",i);
}
return 0;
}
void bfs(int v)
{
for(i=0;i<n;i++)
{
if(a[v][i] && !visited[i])
q[++r]=i;}
if(f<=r)
{
visited[q[f]] =1;
bfs(q[++f]);
}
}
Output:
Implementation of dfs:
#include <stdio.h>
int a[20][20],s[20],visited[20],n,i,j,top=-1;
void dfs(int v)
{
for(i=0;i<n;i++)
{
if(a[v][i] && !visited[i])
s[++top]=i;}
if(top!=-1)
{
visited[s[top]] =1;
dfs(s[top--]);
}
}
int main()
{
int v;
printf("enter the number of vertices: ");
scanf("%d",&n);
printf("enter the adjacency matrix: ");
for(i=0;i<n;i++)
{
for(j=0; j<n; j++)
scanf("%d",&a[i][j]);
}
printf("enter the starting vertex:");
scanf("%d" ,&v);
for(i=0;i<n;i++){
s[i]=0;
visited[i]=0;
}
dfs(v);
printf("the rechable nodes are :");
for(i=0;i<n; i++)
{
if (visited[i])
printf("%d\t",i);
}
return 0;
}
Output:
