3.
Construct Min and Max Heap using arrays, delete any element and display the content of
the Heap.
#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP_SIZE 100
struct Heap {
int arr[MAX_HEAP_SIZE];
int size;
};
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapifyUp(struct Heap *heap, int index) {
int parent = (index - 1) / 2;
while (index > 0 && heap->arr[index] > heap->arr[parent]) {
swap(&heap->arr[index], &heap->arr[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
void heapifyDown(struct Heap *heap, int index) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int largest = index;
if (leftChild < heap->size && heap->arr[leftChild] > heap->arr[largest]) {
largest = leftChild;
}
if (rightChild < heap->size && heap->arr[rightChild] > heap->arr[largest]) {
largest = rightChild;
}
if (largest != index) {
swap(&heap->arr[index], &heap->arr[largest]);
heapifyDown(heap, largest);
}
}
void insertMaxHeap(struct Heap *heap, int key) {
if (heap->size >= MAX_HEAP_SIZE) {
printf("Heap overflow\n");
return;
}
heap->arr[heap->size] = key;
heap->size++;
heapifyUp(heap, heap->size - 1);
}
int deleteMax(struct Heap *heap) {
if (heap->size <= 0) {
printf("Heap underflow\n");
return -1;
}
int maxElement = heap->arr[0];
heap->arr[0] = heap->arr[heap->size - 1];
heap->size--;
heapifyDown(heap, 0);
return maxElement;
}
void displayMaxHeap(struct Heap *heap) {
printf("Max Heap elements: ");
for (int i = 0; i < heap->size; i++) {
printf("%d ", heap->arr[i]);
}
printf("\n");
}
int main() {
struct Heap maxHeap;
maxHeap.size = 0;
insertMaxHeap(&maxHeap, 10);
insertMaxHeap(&maxHeap, 20);
insertMaxHeap(&maxHeap, 15);
insertMaxHeap(&maxHeap, 30);
insertMaxHeap(&maxHeap, 40);
displayMaxHeap(&maxHeap);
int maxElement = deleteMax(&maxHeap);
if (maxElement != -1) {
printf("Deleted max element: %d\n", maxElement);
}
displayMaxHeap(&maxHeap);
return 0;
}
Min Heap Implementation
#include <stdio.h>
#include <stdlib.h>
#define MIN_HEAP_SIZE 100
struct MinHeap {
int arr[MIN_HEAP_SIZE];
int size;
};
void swapMin(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapifyUpMin(struct MinHeap *heap, int index) {
int parent = (index - 1) / 2;
while (index > 0 && heap->arr[index] < heap->arr[parent]) {
swapMin(&heap->arr[index], &heap->arr[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
void heapifyDownMin(struct MinHeap *heap, int index) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int smallest = index;
if (leftChild < heap->size && heap->arr[leftChild] < heap->arr[smallest]) {
smallest = leftChild;
}
if (rightChild < heap->size && heap->arr[rightChild] < heap->arr[smallest]) {
smallest = rightChild;
}
if (smallest != index) {
swapMin(&heap->arr[index], &heap->arr[smallest]);
heapifyDownMin(heap, smallest);
}
}
void insertMinHeap(struct MinHeap *heap, int key) {
if (heap->size >= MIN_HEAP_SIZE) {
printf("Heap overflow\n");
return;
}
heap->arr[heap->size] = key;
heap->size++;
heapifyUpMin(heap, heap->size - 1);
}
int deleteMin(struct MinHeap *heap) {
if (heap->size <= 0) {
printf("Heap underflow\n");
return -1;
}
int minElement = heap->arr[0];
heap->arr[0] = heap->arr[heap->size - 1];
heap->size--;
heapifyDownMin(heap, 0);
return minElement;
}
void displayMinHeap(struct MinHeap *heap) {
printf("Min Heap elements: ");
for (int i = 0; i < heap->size; i++) {
printf("%d ", heap->arr[i]);
}
printf("\n");
}
int main() {
struct MinHeap minHeap;
minHeap.size = 0;
insertMinHeap(&minHeap, 10);
insertMinHeap(&minHeap, 20);
insertMinHeap(&minHeap, 15);
insertMinHeap(&minHeap, 30);
insertMinHeap(&minHeap, 40);
displayMinHeap(&minHeap);
int minElement = deleteMin(&minHeap);
if (minElement != -1) {
printf("Deleted min element: %d\n", minElement);
}
displayMinHeap(&minHeap);
return 0;
}
Output:
Max Heap elements: 40 30 15 10 20
Deleted max element: 40
Max Heap elements: 30 20 15 10
Min Heap elements: 10 20 15 30 40
Deleted min element: 10
Min Heap elements: 15 20 40 30
