From 9891f38ddcca971fa21ab61e7a70832c8c877b0a Mon Sep 17 00:00:00 2001
From: Michael Hunteman <michael@huntm.net>
Date: Sat, 23 Sep 2023 12:53:46 -0500
Subject: Initial commit

---
 min_heap.c | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 113 insertions(+)
 create mode 100644 min_heap.c

(limited to 'min_heap.c')

diff --git a/min_heap.c b/min_heap.c
new file mode 100644
index 0000000..feeaf68
--- /dev/null
+++ b/min_heap.c
@@ -0,0 +1,113 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+int *arr;
+size_t len = 0;
+
+int
+get_parent(int i)
+{
+	return (i - 1) / 2;
+}
+
+int
+get_left_child(int i)
+{
+	return i * 2 + 1;
+}
+
+int
+get_right_child(int i)
+{
+	return i * 2 + 2;
+}
+
+void
+heapify_down(int i)
+{
+	int l = get_left_child(i);
+	int r = get_right_child(i);
+
+	if (i >= len || l >= len) {
+		return;
+	}
+
+	int left_val = arr[l];
+	int right_val = arr[r];
+	int val = arr[i];
+
+	if (right_val > left_val && val > left_val) {
+		arr[i] = left_val;
+		arr[l] = val;
+		heapify_down(l);
+	} else if (left_val > right_val && val > right_val) {
+		arr[i] = right_val;
+		arr[r] = val;
+		heapify_down(r);
+	}
+}
+
+void
+heapify_up(int i)
+{
+	if (i == 0) {
+		return;
+	}
+
+	int p = get_parent(i);
+	int parent_val = arr[p];
+	int child_val = arr[i];
+
+	if (parent_val > child_val) {
+		arr[i] = parent_val;
+		arr[p] = child_val;
+		heapify_up(p);
+	}
+}
+
+void
+insert(int val)
+{
+	arr = realloc(arr, ++len * sizeof(int));
+	arr[len - 1] = val;
+	heapify_up(len - 1);
+}
+
+int
+delete()
+{
+	if (len == 0) {
+		return -1;
+	}
+	int val = arr[0];
+	if (len == 1) {
+		free(arr);
+		return val;
+	}
+
+	arr[0] = arr[--len];
+	heapify_down(0);
+	arr = realloc(arr, len * sizeof(int));
+	return val;
+
+}
+
+int
+main()
+{
+	arr = calloc(len, sizeof(int));
+	insert(5);
+	insert(3);
+	insert(9);
+	insert(7);
+	for (int i = 0; i < len; ++i) {
+		printf("%d ", arr[i]);
+	}
+	printf("\n");
+	delete();
+	for (int i = 0; i < len; ++i) {
+		printf("%d ", arr[i]);
+	}
+	printf("\n");
+	return 0;
+}
-- 
cgit v1.2.3