graphs/piscine/heap/add.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <stdlib.h>

#include "heap.h"

void heapify(int arr[], int n, int i)
{
    if (i == 0)
        return;
    int parent = (i - 1) / 2;
    if (parent >= 0)
    {
        if (arr[i] > arr[parent])
        {
            int tmp = arr[i];
            arr[i] = arr[parent];
            arr[parent] = tmp;
            heapify(arr, n, parent);
        }
    }
}

void add(struct heap *heap, int val)
{
    if (heap->size == heap->capacity)
    {
        heap->array = realloc(heap->array, heap->capacity * 2 * sizeof(int));
        if (heap->array == NULL)
        {
            free(heap);
            return;
        }
        heap->capacity *= 2;
    }

    heap->array[heap->size] = val;
    heap->size++;

    heapify(heap->array, heap->size, heap->size - 1);
}