graphs/piscine/heap/pop.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
40
41
42
43
44
45
46
47
48
49

#include <assert.h>
#include <stdlib.h>

#include "heap.h"

void heapify2(struct heap *h, size_t i)
{
    size_t max = i;
    if (2 * i + 1 < h->size && h->array[2 * i + 1] > h->array[max])
        max = 2 * i + 1;
    if (2 * i + 2 < h->size && h->array[2 * i + 2] > h->array[max])
        max = 2 * i + 2;
    if (max != i)
    {
        int tmp = h->array[i];
        h->array[i] = h->array[max];
        h->array[max] = tmp;
        heapify2(h, max);
    }
}

int pop(struct heap *heap)
{
    assert(heap->size != 0);
    if (heap->size == 1)
    {
        heap->size--;
        return heap->array[0];
    }
    else
    {
        int res = heap->array[0];
        heap->array[0] = heap->array[heap->size - 1];
        heap->size--;
        heapify2(heap, 0);
        if (heap->size < heap->capacity / 2 && heap->capacity > 8)
        {
            heap->array =
                realloc(heap->array, (heap->capacity / 2) * sizeof(int));
            if (heap->array == NULL)
            {
                free(heap);
                return -1;
            }
            heap->capacity /= 2;
        }
        return res;
    }
}