fheap

commit 52c2277f7704ff6317a503089773ff43f216599a
parent 000c5265f306fedffdd99f5959dcbb79ce64098e
Author: olikru <olikru@tkruger.se>
Date:   Thu, 11 Jan 2024 15:54:08 +0100

added delete node operation

Diffstat:
M
fheap.c
 | 
14
++++++++++++++
M
fheap.h
 | 
13
+++++++++++++
M
test_fheap.c
 | 
38
++++++++++++++++++++++++++++++++++++++

3 files changed, 65 insertions(+), 0 deletions(-)
diff --git a/fheap.c b/fheap.c
@@ -254,3 +254,17 @@ void fheap_decrease_value(fheap_t *heap, fnode_t *node, const uint64_t value) {
   if (node->value < (heap->min)->value)
     heap->min = node;
 }
+
+void fheap_delete(fheap_t *heap, fnode_t *node) {
+  node->value = 0; // at least tied minimum
+
+  fnode_t *y = node->parent;
+  if (y != NULL) {
+    fheap_cut(heap, node, y);
+    fheap_cascading_cut(heap, y);
+  }
+
+  heap->min = node;
+  void* _throwaway;
+  fheap_extract_min(&_throwaway, heap);
+}
diff --git a/fheap.h b/fheap.h
@@ -142,4 +142,17 @@ uint64_t fheap_extract_min(void **data, fheap_t *heap);
  */
 void fheap_decrease_value(fheap_t *heap, fnode_t *node, const uint64_t value);
 
+/**
+ * Deletes a node from a Fibonacci heap
+ *
+ * Deletes a node from a Fibonacci heap, freeing and clearing as
+ * neccessary. This assumes that node actually points to a node in the
+ * Fibonacci heap, so in particular node is not NULL and heap is not an
+ * empty heap.
+ *
+ * @param heap the heap to remove node from
+ * @param node the node to delete
+ */
+void fheap_delete(fheap_t *heap, fnode_t *node);
+
 #endif
diff --git a/test_fheap.c b/test_fheap.c
@@ -111,11 +111,49 @@ static void test_fnode_with_decreases() {
   assert(tmp == NULL);
 }
 
+static void test_fnode_delete() {
+  uint64_t values[8] = {1, 5, 7, 0, 10, 3, 4, 11};
+  uint64_t data[8] =   {0, 1, 2, 3,  4, 5, 6,  7};
+  size_t i;
+  uint64_t *tmp;
+  fheap_t heap;
+  fnode_t *nodes[8];
+
+  fheap_init(&heap);
+
+  for(i = 0; i < 8; i++) {
+    nodes[i] = fheap_insert(&heap, values[i], &data[i]);
+  }
+
+  // delete node[2] and node[4]
+  fheap_delete(&heap, nodes[2]);
+  fheap_delete(&heap, nodes[4]);
+
+  assert(fheap_extract_min((void*) &tmp, &heap) == 0);
+  assert(*tmp == 3);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 1);
+  assert(*tmp == 0);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 3);
+  assert(*tmp == 5);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 4);
+  assert(*tmp == 6);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 5);
+  assert(*tmp == 1);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 11);
+  assert(*tmp == 7);
+
+  // now the heap is empty
+  assert(fheap_extract_min((void*) &tmp, &heap) == UINT64_MAX);
+  assert(tmp == NULL);
+}
+
+
 int main() {
   test_fnode_inits();
   test_fnode_clear();
   test_fnode_sort();
   test_fnode_with_decreases();
+  test_fnode_delete();
 
   printf("tests ok\n");
 }