data-structures-and-algorithms/heapTree.c at master · fzehracetin/data-structures-and-algorithms · GitHub

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <stdlib.h>

void insertInHeap(int *n, int HT[], int eleman)
{
    int tmp, i;
    HT[++*n] = eleman;
    i = *n;
    int parent = (i-1)/2;
    while( (i >= 0)&& (HT[parent] > HT[i]) )
    {
        tmp = HT[parent];
        HT[parent] = HT[i];
        HT[i] = tmp;
        i = parent;
        parent = (i-1)/2;
    }
}

int findSmallestChild(int n, int HT[], int i)
{
    if (n > 2*i + 2)
    {
        if ( HT[2*i + 1] > HT[2*i + 2])
            return 2*i + 1;
        else
            return 2*i + 2;
    }
    else if (n > 2*i + 1)
        return 2*i + 1;
    else
        return 0;

}

void removeMin(int *n, int HT[] )
{
    int tmp, i=0, adr;
    tmp = HT[0];
    HT[0] = HT[*n];
    HT[*n--] = tmp;
    adr = findSmallestChild(*n, HT, i);
    while (( adr ) && (HT[i] > HT[ adr]))
    {
        tmp = HT[i];
        HT[i] = HT[adr];
        HT[adr] = tmp;
        i = adr;
        adr = findSmallestChild(*n, HT, i);
    }
}

void downHeap(int HT[], int i, int n)
{
    int tmp, adr;
    adr = findSmallestChild(n, HT, i);
    while (( adr ) && (HT[i] > HT[ adr]))
    {
        tmp = HT[i];
        HT[i] = HT[adr];
        HT[adr] = tmp;
        i = adr;
        adr = findSmallestChild(n, HT, i);
    }
}


int main(int argc, char **argv)
{
    int i, n = 7, m =7;
    int HT1[10] = { 9, 12, 15, 17, 25, 30, 20 };
    int HT2[10] = { 5, 4, 2, 3, 1, 9, 10};

    for (i = 0; i<n ; i++) {
        printf ("%d ", HT1[i]);
    }
    printf("\n");
	insertInHeap(&n , HT1, 3);
    for (i = 0; i<n ; i++) {
        printf ("%d ", HT1[i]);
    }
    printf("\n");
    for (i = 0; i<m ; i++) {
        printf ("%d ", HT2[i]);
    }
    printf("\n");
    heapSort(m, HT2);
    for (i = 0; i<m ; i++) {
        printf ("%d ", HT2[i]);
    }
    printf("\n");
    removeMin(&m, HT2);
    for (i = 0; i<m ; i++) {
        printf ("%d ", HT2[i]);
    }
	return 0;
}