Heap Sort

/*******************************************************************************/
#include <stdio.h>

// Function to perform heapify on a subtree rooted at index i in the given array
void heapify(int arr[], int n, int i) {
    int largest = i;    // Initialize largest as the root
    int left_child = 2 * i + 1;
    int right_child = 2 * i + 2;

    // Compare with left child
    if (left_child < n && arr[left_child] > arr[largest]) {
        largest = left_child;
    }

    // Compare with right child
    if (right_child < n && arr[right_child] > arr[largest]) {
        largest = right_child;
    }

    // If the largest is not the root, swap and continue heapifying
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

// Main function to perform Heap Sort
void heapSort(int arr[], int n) {
    // Build a max-heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract elements from the heap one by one
    for (int i = n - 1; i > 0; i--) {
        // Swap the root (maximum element) with the last element
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Call heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

int main() {
  int arr[50],n,i;
 
  printf("Enter size of the array: ");
  scanf("%d",&n);
  printf("Enter %d elements:\n",n);
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);

    heapSort(arr, n);

    printf("\nSorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
        }

    return 0;
}


/* Heap Sort Alternate Implementation */

#include<stdio.h>
void heapsort(int a[],int n);
void buildheap(int a[],int n);
void extractmax(int a[],int n);
void heapify(int a[],int i, int n);
void swap (int a[],int i, int j);

void heapsort(int a[],int n)
{
//build heap structure
buildheap(a,n);
//extract maxima
extractmax(a,n);
}
void buildheap(int a[],int n)
{
//let heap grow from half size to entire size
for(int i=n/2-1; i>=0; i--)
{
heapify(a,i,n);
}
}
void extractmax(int a[],int n)
{
//n is separator between heap and sorted part
while (n>1)
{
n--;
//put maximum at the end of heap
swap(a,0,n);
//restore heap
heapify(a,0,n);
}
}

//restore heap invariant
void heapify(int a[],int i, int n)
{
int k=2*i+1; //first child of i
while (k<n)
{
//if another child exists and that child is the maximum
if (k+1<n && a[k+1]>a[k]) k++;
if (a[i]>=a[k])
{
return; //heap invariant restored
} 
else
{
//swap element with its child
swap(a,i, k);
//continue with next iteration
i=k;
k=2*i+1;
}
}
}
void swap (int a[],int i, int j)
{
int t;
t= a[i];
a[i] = a[j];
a[j] = t;
}

int main()
{
int size,i;
printf("Enter size of the array: ");
scanf("%d",&size);

int a[size];
printf("Enter %d elements: ",size);
for(i=0;i<size;i++)
scanf("%d",&a[i]);

heapsort(a,size);

printf("Sorted elements: ");
for(i=0;i<size;i++)
printf(" %d",a[i]);

return 0;
}


Comments

Post a Comment

Popular posts from this blog

Data Structure Lab CSL 201 Manual KTU - Dr Binu V P-9847390760

 Dr Binu V P - About Me Data Structures CST 201 KTU Theory Notes  ( Learn Theory Before You Attempt Lab Exercise) SCHEME AND SYLLABUS 1. Polynomial Addition using Arrays 2. Sparse Matrix Representation and sum 3. Stack using Array 4. Queue using Array 5. Circular Queue using Arrays 6. Double Ended Queue  7. Priority Queue  8. Infix to postfix 9. Infix to prefix conversion 10. Prefix to infix conversion 11. Evaluation of postfix expression 12. Singly Linked List 13. Doubly Linked List   14. Stack using Linked List 15. Queue using Linked List 16. Polynomial Addition using Linked list 17. Polynomial Multiplication using Linked List 18. Binary Tree using arrays and traversals 19. Binary Tree using Linked List and Traversal 20. Binary Search Tree Implementation and Traversal 21.Sorting Algorithms       Bubble sort       Exchange sort       Selection Sort       Insertion Sort       Quick Sort ...
Read more

Singly Linked List Implementation

Singly Linked List /**************************************************************************/ #include<stdio.h> #include<stdlib.h> struct Node {  int data;  struct Node *next; }*head=NULL,*tail=NULL,*temp=NULL,*trav=NULL,*prev=NULL; void create() {  temp=(struct Node*)malloc(sizeof(struct Node));  printf("Enter data:");  scanf("%d",&temp->data);  temp->next=NULL;  if(head==NULL)  {   head=temp;   tail=temp;  }  else  {   tail->next=temp;   tail=temp;  } } void display() {  temp=head;  while(temp!=NULL)  {   printf(" %d---->",temp->data);   temp=temp->next;  }  printf(" NULL"); }  void insert_begin()  {      temp=(struct Node*)malloc(sizeof(struct Node));      printf("Enter data:");      scanf("%d",&temp->data);      temp->next=NULL;      if(head...
Read more

Binary search Tree Implementation and Traversal

Binary Search Tree and Operations /******* BST Tree and Operations **********/ #include <stdio.h> #include <stdlib.h>struct Node { int key; struct Node* left; struct Node* right; }; struct Node *root=NULL,*temp=NULL; struct Node* createNode(int key) {      struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));      newNode->key = key;      newNode->left = newNode->right = NULL;      return newNode; } struct Node* insert(struct Node* node, int key) { // Base case: if the tree is empty, create a new node if (node == NULL) {      return createNode(key);      } // Compare the key with the current node's key if (key < node->key) { // Recursively insert into the left subtree      node->left = insert(node->left, key);      } else if (key > node->key) { // Recursively insert into the right subtree    node->...
Read more