C Program: Finding Kth largest element with max Heap

Last update on December 20 2024 13:18:01 (UTC/GMT +8 hours)

Write a C program that uses a max heap to find the kth largest element in an array. Write a function that takes an array and an integer k as input and returns the kth largest element.

Sample Solution:

C Code:

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// Structure to represent a max heap
struct MaxHeap {
    int array[MAX_SIZE]; // Array to store elements in the heap
    int size;            // Current size of the heap
};

// Function to swap two elements in the heap
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify a subtree rooted with node i
void maxHeapify(struct MaxHeap* heap, int i) {
    int largest = i;    // Initialize largest as the root
    int left = 2 * i + 1; // Calculate index of the left child
    int right = 2 * i + 2; // Calculate index of the right child

    // If left child is larger than root
    if (left < heap->size && heap->array[left] > heap->array[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < heap->size && heap->array[right] > heap->array[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        // Swap the found largest element with the root
        swap(&heap->array[i], &heap->array[largest]);

        // Recursively heapify the affected sub-tree
        maxHeapify(heap, largest);
    }
}

// Function to build a max heap
void buildMaxHeap(struct MaxHeap* heap) {
    // Start from the last non-leaf node and heapify all nodes in reverse order
    for (int i = heap->size / 2 - 1; i >= 0; i--) {
        maxHeapify(heap, i);
    }
}

// Function to insert a new element into the max heap
void insert(struct MaxHeap* heap, int value) {
    if (heap->size == MAX_SIZE) {
        printf("Heap is full. Cannot insert.\n");
        return;
    }

    heap->array[heap->size] = value;
    heap->size++;
    buildMaxHeap(heap);
}

// Function to find the kth largest element in an array using a max heap
int findKthLargest(int arr[], int n, int k) {
    struct MaxHeap maxHeap;
    maxHeap.size = 0;

    // Insert the first k elements into the max heap
    for (int i = 0; i < k; i++) {
        insert(&maxHeap, arr[i]);
    }

    // Insert the remaining elements, replacing the root if the current element is larger
    for (int i = k; i < n; i++) {
        if (arr[i] > maxHeap.array[0]) {
            maxHeap.array[0] = arr[i];
            maxHeapify(&maxHeap, 0);
        }
    }

    // The root of the max heap is the kth largest element
    return maxHeap.array[0];
}

int main() {
    int arr[] = {8, 12, 5, 3, 11, 16};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

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

    int kthLargest = findKthLargest(arr, n, k);
    printf("The %dth largest element is: %d\n", k, kthLargest);

    return 0;
}

Output:

Array: 8 12 5 3 11 16
The 3th largest element is: 16

Explanation:

In the exercise above,

Struct Definition:

struct MaxHeap: Represents a max heap using an array. It includes the array to store elements (array) and the current size of the heap (size).

Utility Functions:

swap: Swaps two elements in the heap.
maxHeapify: Ensures a subtree rooted at a given index maintains the max-heap property.
buildMaxHeap: Constructs a max heap from an array.
insert: Inserts a new element into the max heap, maintaining the max-heap property.

Main Function:

Initializes a max heap from an array of integers.
Prints the original array.
Uses a max heap to find the kth largest element in the array.
Prints the kth largest element.a

Flowchart:

C Programming Code Editor:

Previous: Implementing decreaseKey in maximum Heap.