Construct max heap for the following in C language pls:140,80,30,20,10,40,30,60,100,70,160,50,130,110,120

Question:

Construct max heap for the following in C language pls:
140,80,30,20,10,40,30,60,100,70,160,50,130,110,120

Answer:

#include <stdio.h>

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

void max_heapify(int arr[], int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

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

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

  // Swap parent with largest child (if needed) and recursively heapify the subtree
  if (largest != i) {
    swap(&arr[i], &arr[largest]);
    max_heapify(arr, n, largest);
  }
}

void build_max_heap(int arr[], int n) {
  for (int i = n / 2 - 1; i >= 0; i--) {
    max_heapify(arr, n, i);
  }
}

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

int main() {
  int arr[] = {140, 80, 30, 20, 10, 40, 30, 60, 100, 70, 160, 50, 130, 110, 120};
  int n = sizeof(arr) / sizeof(arr[0]);

  build_max_heap(arr, n);

  printf("Max heap: ");
  print_max_heap(arr, n);

  return 0;
}

Use code with caution. Learn morecontent_copy

This code defines three functions:

  • swap: Swaps two integer values.
  • max_heapify: Heapifies a subtree rooted at a given index, ensuring it satisfies the max-heap property.
  • build_max_heap: Builds a max-heap from the entire list by calling max_heapify on all internal nodes in the bottom-up order.

Running this code will print the following output:

Max heap: 160 140 130 100 80 50 120 60 20 70 110 30 40 30 10

This shows that the list is now arranged in a max-heap structure, with the largest element at the root and the remaining elements satisfying the max-heap property.

Leave a Comment