10. Implement the Heap/Shell sort algorithm implemented in C++/Java demonstrating heap/shell data structure with modularity of programming language. 

#include<iostream>
#include<cstring>
using namespace std;
#define size 20
class heap
{
	
public:
	
	void accept()
	{
		int n;
		cout<<".. .. .. .. .. .. .. .. .. .. .. "<<endl;
		cout<<": ENTER NUMBER OF STUDENTS = ";
		cin>>n;
		int a[size];
		cout<<": ENTER MARKS OF EACH STUDENTS  :"<<endl;
		for(int i = 1 ; i <= n ; i++)
		{
			cout<<"Roll NO. "<<i<<" = ";
			cin>>a[i];
		}
		
		heapsort(a,n);
		display(a,n);
	}
	
	void max_heapify(int a[] , int i , int n)
	{
		int temp,left,right,large;
		large = 0;
		left = 2*i;
		right = 2*i+1;
		if( (left <= n) && (a[left] > a[i]))
		
			large = left;
		
		else
			
			large = i;
	
		if( ( right <= n ) && ( a[right] > a[large] ) )
			
			large = right;
		
		if(large != i)
		{
			temp = a[i];
			a[i] = a[large];
			a[large] = temp;
			max_heapify(a,large,n);
		}
	}
			
		
			 
	
	void heapsort(int a[] , int n)
	{
		for(int k = n/2 ; k >= 1 ; k--)
		{
			max_heapify(a,k,n);
		}
		int temp;
		for(int i = n ; i >= 2 ; i--)
		{
			temp = a[1];
			a[1] = a[i];
			a[i] = temp;
			
			max_heapify(a,1,i-1);
		}
	}
	
	void display(int a[] , int n)
	{
		cout<<"\n MINIMUM MARKS = "<<a[1];
		cout<<"\n MAXIMUM MARKS = "<<a[n]<<endl;
	}
		
};

int main()
{
	heap h;
	h.accept();
	return 0;
}

Comments

Post a Comment

Popular posts from this blog

2. Beginning with an empty binary search tree, Construct binary search tree by inserting the values in the order given. After constructing a binary tree -i.Insert new nodeii.Find number of nodes in longest path iii.Minimum data value found inthe tree iv.Change a tree so that the roles of the left and right pointers are swapped at every node v.Search a value

#include<iostream> #include<math.h> using namespace std; struct Bstnode { int data; Bstnode *left = NULL; Bstnode *right = NULL; }; class Btree { int n; int x; int flag; public: Bstnode * root; Btree() { root = NULL; } Bstnode *GetNewNode(int in_data) { Bstnode * ptr = new Bstnode(); ptr->data = in_data; ptr->left = NULL; ptr->right = NULL; return ptr; } Bstnode *insert( Bstnode *temp , int in_data) { if( temp == NULL ) { temp = GetNewNode(in_data); } else if( temp->data > in_data) { temp->left = insert(temp->left , in_data); } else { temp->right = insert( temp->right , in_data); } return temp; } void input() { cout<<"ENTER NUMBER OF ELEMENTS IN THE BST : "; cin>>n; for(int i = 0 ; i < n ; i++) { cout<<"NUMBER = "; cin>>x; root = insert(root , x); } } int search(Bstnode *temp ,int in_data) { if( te...
Read more

1. A book consists of chapters, chapters consist of sections and sections consist of subsections. Construct a tree and print the nodes. Find the time and space requirements of your method.

#include<iostream> using namespace std; struct node { string name; node *B[5]; }; class book { int c,s,sub; public: node *temp = new node; void Getnewnode() { for(int i = 0 ; i<5 ; i++) { temp->B[i] = new node; temp->B[i]->name = "empty"; for(int j=0; j<5; j++) { temp->B[i]->B[j] = new node; temp->B[i]->B[j]->name = "empty"; for(int k = 0 ; k<5; k ++) { temp->B[i]->B[j]->B[k] = new node; temp->B[i]->B[j]->B[k]->name = "empty"; } } } } void add_title() { cout<<": ENTER THE TITLE OF THE BOOK = "; cin>>temp->name; Getnewnode(); } void add_chapter() { string cname; int cnum; cout<<": ENTER NUMBER OF CHAPTERS IN THE BOOK = "; cin>>cnum; c = cnum; for(int i = 0 ; i < cnum ; i++) { cout<<endl<<"Chapter "<...
Read more

4. Write a function to get the number of vertices in an undirected graph and its edges. You may assume thatno edge is input twice. i.Use adjacency list representation of the graph and find runtime of the functionii.Use adjacency matrix representation of the graph and find runtime of the function

#include<iostream> using namespace std; class node { public: char data; node *start = NULL; node *next; void list(char ch) { node *ptr = new node; node *temp = new node; ptr->data = ch; if(start == NULL) { start = ptr; start->next = NULL; } else { temp = start; while(temp->next != NULL) { temp = temp->next; } ptr->next = NULL; temp->next = ptr; } } void displaylist() { node *temp = new node; if(start == NULL) { cout<<"LIST IS EMPTY"<<endl; } else { temp = start; while(temp != NULL) { cout<<temp->data<<"->"; temp = temp->next; } cout<<endl; } } }; class graph { int a[10][10]; char arr[5] = {'A','B','C','D','E'}; int vertices; node al[5]; public: graph() { cout<<"ENTER THE NUMBER OF VERTICES IN THE GRAPH \t::\t"; cin>>ve...
Read more