max_heap.c
trees Implementation
102 lines2023 bytesC
1// Max Heap Implementation
2#include <stdio.h>
3#define MAX 100
4
5struct MaxHeap {
6 int arr[MAX];
7 int size;
8};
9
10void initHeap(struct MaxHeap* heap) {
11 heap->size = 0;
12}
13
14void swap(int* a, int* b) {
15 int temp = *a;
16 *a = *b;
17 *b = temp;
18}
19
20void heapifyUp(struct MaxHeap* heap, int index) {
21 if (index == 0) return;
22
23 int parent = (index - 1) / 2;
24
25 if (heap->arr[index] > heap->arr[parent]) {
26 swap(&heap->arr[index], &heap->arr[parent]);
27 heapifyUp(heap, parent);
28 }
29}
30
31void heapifyDown(struct MaxHeap* heap, int index) {
32 int largest = index;
33 int left = 2 * index + 1;
34 int right = 2 * index + 2;
35
36 if (left < heap->size && heap->arr[left] > heap->arr[largest]) {
37 largest = left;
38 }
39
40 if (right < heap->size && heap->arr[right] > heap->arr[largest]) {
41 largest = right;
42 }
43
44 if (largest != index) {
45 swap(&heap->arr[index], &heap->arr[largest]);
46 heapifyDown(heap, largest);
47 }
48}
49
50void insert(struct MaxHeap* heap, int value) {
51 if (heap->size >= MAX) {
52 printf("Heap is full!\n");
53 return;
54 }
55
56 heap->arr[heap->size] = value;
57 heapifyUp(heap, heap->size);
58 heap->size++;
59}
60
61int extractMax(struct MaxHeap* heap) {
62 if (heap->size == 0) {
63 printf("Heap is empty!\n");
64 return -1;
65 }
66
67 int max = heap->arr[0];
68 heap->arr[0] = heap->arr[heap->size - 1];
69 heap->size--;
70 heapifyDown(heap, 0);
71
72 return max;
73}
74
75void display(struct MaxHeap* heap) {
76 printf("Max Heap: ");
77 for (int i = 0; i < heap->size; i++) {
78 printf("%d ", heap->arr[i]);
79 }
80 printf("\n");
81}
82
83int main() {
84 struct MaxHeap heap;
85 initHeap(&heap);
86
87 insert(&heap, 10);
88 insert(&heap, 20);
89 insert(&heap, 15);
90 insert(&heap, 40);
91 insert(&heap, 50);
92 insert(&heap, 100);
93 insert(&heap, 25);
94
95 display(&heap);
96
97 printf("Extracted max: %d\n", extractMax(&heap));
98 display(&heap);
99
100 return 0;
101}
102