max_heap.c

trees Implementation

102 lines
2023 bytes
C
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