Life Hacks


      

Write a program of the Heap Sort.



#include<iostream.h>

#include<conio.h>

int arr[20], n;

class heap

{

private:

int loc, num, par; /* local variable */

public:

void del_root(int);

void create_heap( );

void display( );

void heap_sort( );

void insert(int, int);

};

void heap :: insert(int num, int loc)

{

int par; /* local variable */

while(loc > 0)

{

par = (loc – 1) / 2;

if(num <= arr[par])

{

arr[loc] = num;

return;

}

arr[loc] = arr[par];

loc = par;

} /* End of while loop*/

arr[0] = num;

}

void heap :: display()

{

int i; /* local variable */

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

{

cout << arr[i] << “ ”;

} /* End of for loop*/

}

void heap :: create_heap()

{

int i; /* local variable */

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

{

insert(arr[i], i);

cout << “ ”;

} /* End of for loop*/

}

void heap :: heap_sort()

{

int last; /* local variable */

for(last = n – 1; last > 0; last –)

{

del_root(last);

cout << “ ”;

} /* End of for loop*/

}

void heap :: del_root(int last)

{

int left, right, i, temp; /* local variable */

i = 0;

temp = arr[i];

arr[i] = arr[last];

arr[last] = temp;

left = 2 * i + 1;

right = 2 * i + 2;

while(right > last)

{

if(arr[i] <= arr[left] && arr[i] >= arr[right])

return;

if(arr[right] <= arr[left])

{

temp = arr[i];

arr[i] = arr[left];

arr[left] = temp;

i = left;

}

else

{

temp = arr[i];

arr[i] = arr[right];

arr[right] = temp;

i = right;

}

left = 2 * i + 1;

right = 2 * i + 2;

} /* End of while loop*/

if(left == last – 1 && arr[i] < arr[left])

{

temp = arr[i];

arr[i] = arr[left];

arr[left] = temp;

}

}

void main( ) /* main start */

{

int i; /* local variable */

clrscr( );

cout << “Enter the number of elements :”; // inserting the numbers

cin >> n;

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

{

cout << “Enter elements is : ” << i + 1 << “ \n ”;

cin >> arr[i];

} /* End of for loop*/

cout << “ Entered list is :”;

heap h;

h.display( );

h.create_heap( ); // creating the heap

cout << “ Heap is :”;

h.display( );

h.heap_sort( ); // sorted the array

cout << “ Sorted list is :”;

h.display( );

getch( );

}

Output:-

clip_image002

Leave a Reply