Skip to content

Commit 45e212d

Browse files
trmendesthuva4
trmendes
authored and
thuva4
committed
Heapsort (C) (thuva4#214)
* Add a Heap Struct + Heap sort - C * New Directory
1 parent a4d9ccc commit 45e212d

4 files changed

Lines changed: 275 additions & 0 deletions

File tree

‎HeapSort/C/Makefile‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
# project name (generate executable with this name)
2+
TARGET = lab
3+
4+
CC = gcc
5+
# compiling flags here
6+
CFLAGS = -std=c99 -g -Wall -I.
7+
8+
LINKER = gcc
9+
# linking flags here
10+
LFLAGS = -Wall -g -I. -lm
11+
12+
# change these to proper directories where each file should be
13+
OBJDIR = obj
14+
BINDIR = bin
15+
16+
SOURCES := $(wildcard *.c)
17+
INCLUDES := $(wildcard *.h)
18+
OBJECTS := $(SOURCES:%.c=%.o)
19+
rm = rm -f
20+
21+
22+
$(TARGET): $(OBJECTS)
23+
@$(LINKER) $(OBJECTS) $(LFLAGS) -o $@
24+
@echo "Linking complete!"
25+
26+
$(OBJECTS): %.o : %.c
27+
@$(CC) $(CFLAGS) -c $< -o $@
28+
@echo "Compiled "$<" successfully!"
29+
30+
.PHONY: clean
31+
clean:
32+
@$(rm) $(OBJECTS) $(TARGET) 01.out 02.out 03.out 04.out 07.out
33+
@echo "Cleanup complete!"
34+
35+
.PHONY: run
36+
run:
37+
@./$(TARGET)

‎HeapSort/C/heap.c‎

Lines changed: 168 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,168 @@
1+
#include <stdlib.h>
2+
#include <stdint.h>
3+
#include <stdio.h>
4+
#include <string.h>
5+
#include "heap.h"
6+
7+
heap_ctrl_t * hp_create(size_t size) {
8+
heap_ctrl_t * h = (heap_ctrl_t *) calloc(1, sizeof(heap_ctrl_t));
9+
h->array = (data_t **) calloc(size, sizeof(data_t *));
10+
h->size = size;
11+
return h;
12+
}
13+
14+
void hp_destroy(heap_ctrl_t ** heap) {
15+
if (*heap == (heap_ctrl_t *) NULL)
16+
return;
17+
18+
memset((*heap)->array, 0x00, (*heap)->size * sizeof(data_t *));
19+
free((*heap)->array);
20+
21+
memset(*heap, 0x00, sizeof(heap_ctrl_t));
22+
free(*heap);
23+
24+
heap = NULL;
25+
}
26+
27+
int32_t hp_insert(heap_ctrl_t * heap, int32_t data) {
28+
if (heap == (heap_ctrl_t *) NULL)
29+
return ERR_HEAP_NULL;
30+
31+
if (heap->next == heap->size - 1)
32+
return ERR_HEAP_FULL;
33+
34+
int32_t parent, leaf;
35+
data_t * datas = (data_t *) calloc(1, sizeof(data_t));
36+
datas->data = data;
37+
38+
heap->array[heap->next] = datas;
39+
parent = heap->next;
40+
leaf = heap->next;
41+
42+
while (parent != 0) {
43+
if (parent % 2 == 0)
44+
parent = (parent - 2) / 2;
45+
else
46+
parent = (parent - 1) / 2;
47+
48+
49+
if (heap->array[parent]->data <= data) {
50+
heap->array[leaf] = heap->array[parent];
51+
heap->array[parent] = datas;
52+
leaf = parent;
53+
}
54+
}
55+
++heap->next;
56+
57+
return SUCCESS;
58+
}
59+
60+
int32_t hp_remove(heap_ctrl_t * heap) {
61+
if (heap == (heap_ctrl_t *) NULL)
62+
return ERR_HEAP_NULL;
63+
64+
if (heap->next == 0)
65+
return ERR_HEAP_EMPTY;
66+
67+
if (heap->array[0] != (data_t *) NULL)
68+
free(heap->array[0]);
69+
70+
--heap->next;
71+
heap->array[0] = heap->array[heap->next];
72+
heap->array[heap->next] = (data_t *) NULL;
73+
74+
hp_heapfy(heap);
75+
76+
return SUCCESS;
77+
}
78+
79+
int32_t hp_heapfy(heap_ctrl_t * heap) {
80+
if (heap == (heap_ctrl_t *) NULL)
81+
return ERR_HEAP_NULL;
82+
83+
size_t l, r;
84+
int32_t parent = 0;
85+
86+
while (1) {
87+
l = LEFT(parent);
88+
r = RIGHT(parent);
89+
90+
if (heap->array[r] == (data_t *) NULL) {
91+
if (heap->array[l] == (data_t *) NULL)
92+
break;
93+
if (heap->array[l]->data >= heap->array[parent]->data) {
94+
hp_swap(&(heap)->array[l], &(heap)->array[parent]);
95+
parent = l;
96+
} else {
97+
break;
98+
}
99+
} else {
100+
if ((heap->array[l]->data >= heap->array[parent]->data) && (heap->array[l]->data > heap->array[r]->data)) {
101+
hp_swap(&(heap)->array[l], &(heap)->array[parent]);
102+
parent = l;
103+
} else if ((heap->array[r]->data >= heap->array[parent]->data) && (heap->array[r]->data > heap->array[l]->data)) {
104+
hp_swap(&(heap)->array[r], &(heap)->array[parent]);
105+
parent = r;
106+
} else {
107+
break;
108+
}
109+
}
110+
}
111+
112+
return SUCCESS;
113+
}
114+
115+
void hp_swap(data_t ** a, data_t ** b) {
116+
data_t * tmp;
117+
tmp = *a;
118+
*a = *b;
119+
*b = tmp;
120+
}
121+
122+
int32_t hp_sort(heap_ctrl_t * heap) {
123+
if (heap == (heap_ctrl_t *) NULL)
124+
return ERR_HEAP_NULL;
125+
126+
data_t ** sorted = (data_t **) calloc(heap->size, sizeof(data_t *));
127+
128+
int32_t i;
129+
130+
for (i = (heap->next - 1); i >= 0; --i) {
131+
sorted[i] = heap->array[0];
132+
heap->array[0] = heap->array[i];
133+
heap->array[i] = (data_t *) NULL;
134+
135+
hp_heapfy(heap);
136+
}
137+
138+
for (i = 0; i < (int32_t) heap->next; ++i)
139+
heap->array[i] = sorted[i];
140+
141+
memset(sorted, 0x00, heap->size * sizeof(data_t *));
142+
free(sorted);
143+
144+
return SUCCESS;
145+
}
146+
147+
int32_t hp_get_head(heap_ctrl_t * heap) {
148+
if (heap == (heap_ctrl_t *) NULL)
149+
return ERR_HEAP_NULL;
150+
if (heap->next == 0)
151+
return ERR_HEAP_EMPTY;
152+
153+
return heap->array[0]->data;
154+
}
155+
156+
void hp_print(heap_ctrl_t * heap) {
157+
if (heap == (heap_ctrl_t *) NULL)
158+
return;
159+
160+
size_t i;
161+
162+
printf("[");
163+
for (i = 0; i < heap->next + 1; ++i) {
164+
if (heap->array[i] != (data_t *) NULL)
165+
printf("%d ", heap->array[i]->data);
166+
}
167+
printf("]\n");
168+
}

‎HeapSort/C/heap.h‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
#ifndef __HEAP_H__
2+
#define __HEAP_H__
3+
4+
#include <stdint.h>
5+
#include <stdlib.h>
6+
7+
#define ERR_HEAP_EMPTY -3
8+
#define ERR_HEAP_FULL -2
9+
#define ERR_HEAP_NULL -1
10+
#define SUCCESS EXIT_SUCCESS
11+
12+
#define LEFT(N) ( (2 * N) + 1 )
13+
#define RIGHT(N) ( (2 * N) + 2 )
14+
15+
typedef struct data_s {
16+
int32_t data;
17+
} data_t;
18+
19+
typedef struct heap_ctrl_s {
20+
data_t ** array;
21+
size_t size;
22+
uint32_t next;
23+
} heap_ctrl_t;
24+
25+
heap_ctrl_t * hp_create (size_t size);
26+
void hp_destroy (heap_ctrl_t ** heap);
27+
int32_t hp_insert (heap_ctrl_t * heap, int32_t data);
28+
int32_t hp_remove (heap_ctrl_t * heap);
29+
void hp_swap (data_t ** a, data_t ** b);
30+
int32_t hp_heapfy (heap_ctrl_t * heap);
31+
int32_t hp_get_head (heap_ctrl_t * heap);
32+
int32_t hp_sort (heap_ctrl_t * heap);
33+
void hp_print (heap_ctrl_t * heap);
34+
#endif

‎HeapSort/C/main.c‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
#include <stdint.h>
2+
#include <stdlib.h>
3+
#include "heap.h"
4+
5+
int32_t main() {
6+
heap_ctrl_t * h = hp_create(11);
7+
hp_insert(h, 88);
8+
hp_insert(h, 85);
9+
hp_insert(h, 83);
10+
hp_insert(h, 72);
11+
hp_insert(h, 73);
12+
hp_insert(h, 42);
13+
hp_insert(h, 57);
14+
hp_insert(h, 6);
15+
hp_insert(h, 48);
16+
hp_insert(h, 60);
17+
hp_print(h);
18+
hp_sort(h);
19+
hp_print(h);
20+
hp_remove(h);
21+
hp_print(h);
22+
hp_remove(h);
23+
hp_print(h);
24+
hp_remove(h);
25+
hp_print(h);
26+
hp_remove(h);
27+
hp_print(h);
28+
hp_remove(h);
29+
hp_print(h);
30+
hp_remove(h);
31+
hp_print(h);
32+
hp_remove(h);
33+
hp_print(h);
34+
hp_destroy(&h);
35+
return EXIT_SUCCESS;
36+
}

0 commit comments

Comments
 (0)