1#include "meldable_heap.h"
  2#include <stddef.h>
  3#include <stdio.h>
  4#include <stdlib.h>
  5
  6/**
  7 * Compares two integers and returns -1, 0, 1.
  8 * If a is equal to b then 0 is returned.
  9 * If a is greater than b then 1 is returned.
 10 * If a is less than b then -1 is returned.
 11 *
 12 * @param a An integer
 13 * @param b Another integer
 14 * @return Returns 0, 1, or -1.
 15 */
 16static int compare(int a, int b) { return (a < b) ? -1 : ((a > b) ? 1 : 0); }
 17
 18/**
 19 * Print a visual representation of a heap.
 20 *
 21 * @param heap The subtree to print
 22 * @param level The level in the heap that this subtree is in
 23 */
 24static void print_tree(MeldableHeap *heap, int level) {
 25  for (int i = 0; i < level; i++)
 26    printf(" ");
 27
 28  if (heap) {
 29    printf("(%d)\n", heap->value);
 30
 31    if (!heap->left && !heap->right)
 32      return;
 33    print_tree(heap->left, level + 1);
 34    print_tree(heap->right, level + 1);
 35  } else {
 36    printf("( )\n");
 37  }
 38}
 39
 40/**
 41 * Initializes an instance of an meldable heap.
 42 *
 43 * @param value The value to assign to the new node in the heap.
 44 * @return Returns the new heap node instance.
 45 */
 46MeldableHeap *meldable_heap_initialize(int value) {
 47  MeldableHeap *heap = malloc(sizeof(MeldableHeap));
 48  heap->left = NULL;
 49  heap->right = NULL;
 50  heap->parent = NULL;
 51  heap->value = value;
 52  return heap;
 53};
 54
 55/**
 56 * Adds a new value into a heap.
 57 *
 58 * @param heap The subtree to attempt to insert a new value into.
 59 * @param value The value to insert.
 60 * @return Returns the new root of the subtree.
 61 */
 62MeldableHeap *meldable_heap_add(MeldableHeap *heap, int value) {
 63  MeldableHeap *root =
 64      meldable_heap_merge(meldable_heap_initialize(value), heap);
 65  root->parent = NULL;
 66  return root;
 67}
 68
 69/**
 70 * Merges to meldable heaps into a single heap and returns the
 71 * root of the new heap.
 72 *
 73 * @param h1 A heap
 74 * @param h2 Another heap
 75 * @return Returns the merged heap
 76 */
 77MeldableHeap *meldable_heap_merge(MeldableHeap *h1, MeldableHeap *h2) {
 78  if (h1 == NULL)
 79    return h2;
 80  if (h2 == NULL)
 81    return h1;
 82
 83  if (compare(h2->value, h1->value) < 0)
 84    return meldable_heap_merge(h2, h1);
 85
 86  if (rand() % 2 == 0) {
 87    h1->left = meldable_heap_merge(h1->left, h2);
 88    h1->left->parent = h1;
 89  } else {
 90    h1->right = meldable_heap_merge(h1->right, h2);
 91    h1->right->parent = h1;
 92  }
 93  return h1;
 94}
 95
 96/**
 97 * Prints a visual inspection of
 98 * a heap for debugging purposes to stdout.
 99 *
100 * @param heap The heap to visualize
101 */
102void meldable_heap_inspect(MeldableHeap *heap) { print_tree(heap, 0); }
103
104/**
105 * Removes a value from a meldable heap.
106 *
107 * @param heap The subtree to remove
108 */
109void meldable_heap_remove(MeldableHeap *heap) {
110  MeldableHeap *replacement = meldable_heap_merge(heap->left, heap->right);
111
112  if (replacement)
113    replacement->parent = heap->parent;
114
115  if (!heap->parent)
116    return;
117
118  if (heap->parent->left == heap)
119    heap->parent->left = replacement;
120  else
121    heap->parent->right = replacement;
122}