BUPT-homework/semester3/pset3/7-2-Binomial-Queue-TakeTwo.c

// 15:10 - 15:42 - 32min
#include <stdio.h>
#include <stdlib.h>
#define MAX 100

typedef struct node {
  int val, degree;
  struct node *child, *sibling;
} node;

typedef struct list {
  node **arr;
  int size;
} list;

node *newNode(int val) {
  node *n = malloc(sizeof(node));
  n->val = val;
  n->degree = 0;
  n->child = NULL;
  n->sibling = NULL;

  return n;
}

list *newList(int capacity) {
  list *li = malloc(sizeof(list));

  li->arr = malloc(sizeof(node *) * capacity);
  li->size = 0;

  return li;
}

void pushBack(list *li, node *n) { li->arr[li->size++] = n; }

list *erase(list *li, int loc) {
  for (int i = loc, size = li->size; i < size - 1; i++) {
    li->arr[i] = li->arr[i + 1];
  }
  li->size--;
  return li;
}

list *unionList(list *l, list *r) {
  int i = 0, j = 0;
  list *li = newList(MAX);

  while (i < l->size && j < r->size) {
    if (l->arr[i]->degree < r->arr[j]->degree) {
      pushBack(li, l->arr[i++]);
    } else {
      pushBack(li, r->arr[j++]);
    }
  }

  while (i < l->size) {
    pushBack(li, l->arr[i++]);
  }
  while (j < r->size) {
    pushBack(li, r->arr[j++]);
  }

  return li;
}

void swapNode(node *l, node *r) {
  node tmp = *l;
  *l = *r;
  *r = tmp;
}

node *merge(node *l, node *r) {
  // remember, smaller one goes up
  if (l->val > r->val) {
    swapNode(l, r);
  }
  r->sibling = l->child;
  l->child = r;

  l->degree++;

  return l;
}

list *adjust(list *li) {
  if (li->size == 1) {
    return li;
  }
  int i = 0, j = 0, k = 0;
  if (li->size == 2) {
    j = 1;
    k = li->size;
  } else {
    j = 1;
    k = 2;
  }

  while (i < li->size) {
    if (j == li->size) {
      i++;
    } else if (li->arr[i]->degree < li->arr[j]->degree) {
      i++;
      j++;
      if (k < li->size) {
        k++;
      }
    } else if (k < li->size && li->arr[i]->degree == li->arr[j]->degree &&
               li->arr[i]->degree == li->arr[k]->degree) {
      i++;
      j++;
      k++;
    } else if (li->arr[i]->degree == li->arr[j]->degree) {
      // remember, no need to do anything else.
      li->arr[i] = merge(li->arr[i], li->arr[j]);
      erase(li, j);
    }
  }
  return li;
}

list *insert(list *li, int val) {
  node *n = newNode(val);
  list *tmp = newList(MAX);
  pushBack(tmp, n);

  tmp = unionList(li, tmp);
  return adjust(tmp);
}

int getDigits(int i) {
  int count = 0;
  while (i) {
    i /= 10;
    count++;
  }

  return count;
}

void printLevel(node *n, int level) {
  if (n) {
    printLevel(n->sibling, level);
    if (level == 1) {
      printf("%d,", n->val);
    } else {
      printLevel(n->child, level - 1);
    }
  }
}

void printHeap(node *n) {
  int level = 0;
  for (node *ptr = n; ptr != NULL; ptr = ptr->child) {
    printLevel(n, ++level);
  }
}

void printTree(list *li, int k) {
  int present = 0;
  for (int i = 0, size = li->size; i < size; i++) {
    if (li->arr[i]->degree == k) {
      printHeap(li->arr[i]);
      present = 1;
    }
  }

  if (!present) {
    printf("0,\n");
  }
}

int main(void) {
  char buf[MAX];
  fgets(buf, MAX, stdin);
  list *li = newList(MAX);

  int tmp;
  int offset = 0;
  while (sscanf(buf + offset, "%d,", &tmp) != EOF) {
    li = insert(li, tmp);         // remember li =
    offset += getDigits(tmp) + 1; // remember to + 1
  }

  int k;
  scanf("%d", &k);
  printTree(li, k);

  return 0;
}