aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Liodden <eriklio@stud.ntnu.no>2017-12-03 15:40:32 +0100
committerErik Liodden <eriklio@stud.ntnu.no>2017-12-03 15:52:29 +0100
commitc14d266eb7b1f19aebcc20891f86c84f5105d1b4 (patch)
tree07977ebd394186f19e0364249331e11a83709392
parenta8ae1cb3664f8fa1c8f25ed4bedf7709e1fc49f1 (diff)
downloadalgdat-c14d266eb7b1f19aebcc20891f86c84f5105d1b4.tar.gz
add heap data structure
add a generic heap data structure. the heap is initialized with: struct heap h; heap_init(&h, elem_size, freefn, compar); to add elements to the heap use: heap_max_heap_insert(struct heap *h, void *key); (aka the most stupid name ever. should probably change that later.) and to get the maximum element use: heap_extract_max(struct heap *h, void *target_addr); heap_sort is implemented in heap.c and will sort an already existing array in place in O(n lg n) time. if the heap is initialized by the user (heap_init), the user must run heap_dispose() when the heap is no longer in use, to free up allocated space.
-rw-r--r--Makefile4
-rw-r--r--heap.c158
-rw-r--r--sort.h2
-rw-r--r--structure.h41
4 files changed, 194 insertions, 11 deletions
diff --git a/Makefile b/Makefile
index 67f77f4..86bafe3 100644
--- a/Makefile
+++ b/Makefile
@@ -6,9 +6,9 @@ AR=ar
PROG= oving1
-LIB_OBJS=stack.o queue.o llist.o io.o misc.o sort.o
+LIB_OBJS=stack.o queue.o llist.o io.o misc.o sort.o heap.o
LIB_FILE=libalgdat.a
-LIB_H=structure.h misc.h io.h
+LIB_H=structure.h misc.h io.h sort.h
LIBS = $(LIB_FILE)
all: $(PROG)
diff --git a/heap.c b/heap.c
new file mode 100644
index 0000000..9ef3945
--- /dev/null
+++ b/heap.c
@@ -0,0 +1,158 @@
+/*
+ * heap.c
+ * implementation of a generic heap
+ *
+ * Erik Liodden
+ */
+
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+#include "structure.h"
+#include "misc.h"
+
+#define ceil(a, b) (a % b) ? a/b + 1 : a/b
+#define parent(i) ceil(i, 2) - 1
+#define right(i) 2*i + 1
+#define left(i) 2*i + 2
+
+static void grow_heap(struct heap *h)
+{
+ h->alloc_length *= 2;
+ h->elems = realloc(h->elems, h->alloc_length * h->elem_size);
+ assert(h->elems != NULL);
+}
+
+static void heap_init_from_array(struct heap *h, void *elems, int nel, size_t
+ elem_size, void (*freefn)(void *), int (*compar)(const void *,
+ const void *))
+{
+ h->elem_size = elem_size;
+ h->log_length = nel-1;
+ h->alloc_length = nel-1;
+ h->elems = elems;
+ h->freefn = freefn;
+ h->compar = compar;
+}
+
+void heap_init(struct heap *h, size_t elem_size, void (*freefn)(void *),
+ int (*compar)(const void *, const void *))
+{
+ h->elem_size = elem_size;
+ h->log_length = 0;
+ h->alloc_length = 4;
+ h->elems = allocate(h->alloc_length * elem_size);
+ h->freefn = freefn;
+ h->compar = compar;
+}
+
+void heap_dispose(struct heap *h)
+{
+ int i;
+ if (h->freefn) {
+ for (i = 0; i < h->log_length; i++)
+ h->freefn((char *)h->elems + (i * h->elem_size));
+ }
+ free(h->elems);
+}
+
+void heap_max_heapify(struct heap *h, int i)
+{
+ int largest;
+ int l = left(i);
+ int r = right(i);
+
+ if (l <= h->log_length && h->compar((char *)h->elems + l*h->elem_size,
+ (char *)h->elems + i*h->elem_size) > 0)
+ largest = l;
+ else
+ largest = i;
+ if (r <= h->log_length && h->compar((char *)h->elems + r*h->elem_size,
+ (char *)h->elems + largest*h->elem_size) > 0)
+ largest = r;
+ if (largest != i) {
+ swap((char *)h->elems + i*h->elem_size, (char *)h->elems +
+ largest*h->elem_size, h->elem_size);
+ heap_max_heapify(h, largest);
+ }
+}
+
+void heap_build_max_heap(struct heap *h)
+{
+ int i;
+ for (i = h->log_length/2; i >= 0; i--)
+ heap_max_heapify(h, i);
+}
+
+void heap_maximum(struct heap *h, void *elem_addr)
+{
+ if (h->log_length >= 0)
+ memcpy(elem_addr, h->elems, h->elem_size);
+}
+
+void heap_extract_max(struct heap *h, void *elem_addr)
+{
+ if (h->log_length <= 0) {
+ fprintf(stderr, "error: underflow. heap empty\n");
+ exit(EXIT_FAILURE);
+ }
+ heap_maximum(h, elem_addr);
+ memcpy(h->elems, (char *)h->elems + (h->log_length-1)*h->elem_size,
+ h->elem_size);
+ h->log_length--;
+ heap_max_heapify(h, 0);
+}
+
+void heap_increase_key(struct heap *h, int i, void *key)
+{
+ int p;
+ if (h->compar(key, (char *)h->elems + i*h->elem_size) < 0) {
+ fprintf(stderr, "new key is smaller than previos key\n");
+ exit(EXIT_FAILURE);
+ }
+ memcpy((char *)h->elems + i*h->elem_size, key, h->elem_size);
+ p = parent(i);
+ while (i > 0 && h->compar((char *)h->elems + p*h->elem_size,
+ (char *)h->elems + i*h->elem_size) < 0) {
+ swap((char *)h->elems + i*h->elem_size, (char *)h->elems +
+ p*h->elem_size, h->elem_size);
+ i = parent(i);
+ p = parent(i);
+ }
+}
+
+void heap_max_heap_insert(struct heap *h, void *key)
+{
+ int i, p;
+ if (h->log_length == h->alloc_length)
+ grow_heap(h);
+ void *target = (char *)h->elems + (h->log_length * h->elem_size);
+ memcpy(target, key, h->elem_size);
+ i = h->log_length;
+ p = parent(i);
+ while (i > 0 && h->compar((char *)h->elems + p*h->elem_size,
+ (char *)h->elems + i*h->elem_size) < 0) {
+ swap((char *)h->elems + i*h->elem_size, (char *)h->elems +
+ p*h->elem_size, h->elem_size);
+ i = parent(i);
+ p = parent(i);
+ }
+ h->log_length++;
+}
+
+void heap_sort(void *base, size_t nel, size_t width,
+ int (*compar)(const void *, const void *))
+{
+ int i;
+ struct heap h;
+
+ heap_init_from_array(&h, base, nel, width, NULL, compar);
+ heap_build_max_heap(&h);
+ for (i = nel-1; i > 0; i--) {
+ swap((char *)base, (char *)base + i*width, width);
+ h.log_length--;
+ heap_max_heapify(&h, 0);
+ }
+}
diff --git a/sort.h b/sort.h
index 5c6ea0e..3106162 100644
--- a/sort.h
+++ b/sort.h
@@ -18,6 +18,8 @@
void insertion_sort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *));
+void heap_sort(void *base, size_t nel, size_t width,
+ int (*compar)(const void *, const void *));
#endif /* SORT_H */
diff --git a/structure.h b/structure.h
index 6d45609..126dd41 100644
--- a/structure.h
+++ b/structure.h
@@ -11,9 +11,9 @@
#ifndef STRUCTURE_H
#define STRUCTURE_H
-/****************************************************************************
- * Stack *
- ****************************************************************************/
+/*
+ * Stack
+ */
struct stack {
void *elems;
@@ -32,9 +32,9 @@ void stack_get(struct stack *s, void *elem_addr, int loc);
void stack_replace(struct stack *s, void *elem_addr, int loc);
int stack_length(struct stack *s);
-/****************************************************************************
- * Queue *
- ****************************************************************************/
+/*
+ * Queue
+ */
struct queue {
void *elems;
@@ -52,9 +52,9 @@ void queue_enqueue(struct queue *q, void *elem_addr);
void queue_dequeue(struct queue *q, void *elem_addr);
int queue_length(struct queue *q);
-/****************************************************************************
- * Circular doubly linked list *
- ****************************************************************************/
+/*
+ * Circular doubly linked list
+ */
struct llist {
struct llist_node *nil;
@@ -80,4 +80,27 @@ void llist_remove_node(struct llist_node *node);
void llist_get_elem(struct llist_node *node, void *elem_addr);
void llist_dispose(struct llist *l);
+/*
+ * heap
+ */
+
+struct heap {
+ void *elems;
+ size_t elem_size;
+ int log_length;
+ int alloc_length;
+ void (*freefn)(void *);
+ int (*compar)(const void *, const void *);
+};
+
+void heap_init_empty(struct heap *h, size_t elem_size, void (*freefn)(void *),
+ int (*compar)(const void *, const void *));
+void heap_dispose(struct heap *h);
+void heap_max_heapify(struct heap *h, int pos);
+void heap_build_max_heap(struct heap *h);
+void heap_maximum(struct heap *h, void *elem_addr);
+void heap_extract_max(struct heap *h, void *elem_addr);
+void heap_increase_key(struct heap *h, int pos, void *key);
+void heap_max_heap_insert(struct heap *h, void *key);
+
#endif /* STRUCTURE_H */