Метод BubbleUp в реализации Heap в c

Question

Я разместил здесь свою реализацию кучи и получил некоторую столь необходимую помощь с моей функцией add (), за которую я очень благодарен, но я все еще получаю недопустимые операции чтения и утечки памяти, и могу использовать дополнительную помощь.

заголовочный файл heap.h:

#ifndef HEAP_H
#define HEAP_H
#include <stdbool.h>
struct Entry {
  int key;
  char* value;
};

typedef struct Entry Entry;

struct Heap {
  int capacity;
  int size;
  Entry** elements;
};

typedef struct Heap Heap;

Heap* makeHeap(int capacity);
void add(Heap* heap, int priority, char* value);
char* removeMin(Heap* heap);
char* peek(Heap* heap);
int size(Heap* heap);
void cleanupHeap(Heap* h);

#endif

файл heap.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "heap.h"

Heap* makeHeap(int capacity) {
   //Make the heap
   Heap* theHeap = calloc(1, sizeof(Heap));
   //set its capacity to param
   theHeap->capacity = capacity;
   //inital size is 0
   theHeap->size = 0;
   //elements contains pointers (references) to Entry objects.
   theHeap->elements = calloc(capacity, sizeof(Entry*));
   //iterate capacity times allocating an entry reference for each element to be placed
   int i = 0;
   for(; i < capacity; i++) {
     theHeap-> elements[i] = calloc(1, sizeof(Entry));
   }

   return theHeap;
}

void expandCapacity(Heap* h) {
   Entry** oldcontents = h->elements;
   Entry** newarr = calloc(h->capacity * 2, sizeof(Entry*));
   int i = 0;
   for(; i < h->size; i += 1) {
      newarr[i] = h->elements[i];
   }

   h->capacity = h->capacity * 2;
   h->elements = newarr;
   free(oldcontents);
}

void add(Heap* h, int priority, char* val) {
  if (h->size >= h->capacity) {
    expandCapacity(h);
  }
  //insert at end of storage array and bubble up
  Entry* toAdd = calloc(1, sizeof(Entry));
  toAdd->key = priority;
  toAdd->value = val;
  h->elements[h->size]=toAdd;
  h->size += 1;
  bubbleUp(h, h->size);
}

void bubbleUp(Heap* h, int index) {
   if(index <= 0) { return; }
   Entry* e = h->elements[index];
   Entry* parent = h->elements[(index-1)/2];
   int comp = strcmp(e->value, parent->value);
   if(comp > 0) {
     swap(h, index, parent->key);
     bubbleUp(h, parent->key);
   }
   else {
     return;
   }
}

void swap(Heap* h, int index1, int index2) {
   Entry* tmp = h->elements[index1];
   h->elements[index1] = h->elements[index2];
   h->elements[index2] = tmp;
}
void cleanupHeap(Heap* h) {
   int i = 0;
   for (; i < h->capacity; i++) {
      free(h->elements[i]);
   }
   free(h->elements);
   free(h);
}

bubbleUp () и swap () были заданы функции в Java, поэтому всеМне нужно было адаптировать их для этого проекта для работы с файлом heap.h и, конечно, перевести их в c.Я уверен в add () из моей предыдущей помощи и swap (), так как это кажется довольно простым, но я думаю, что есть проблема с моим переводом в c для bubbleUp ().Любой вклад приветствуется.

Java-код:

 void bubbleUp(int index) {
    if(index <= 0) { return; }
    Entry<K,V> e = this.entries.get(index);  
    Entry<K,V> parent = this.entries.get(parent(index));  
    int comp = this.comparator.compare(e.key, parent.key);
    if(comp > 0) {
      swap(index, parent(index));
      bubbleUp(parent(index));
    }
    else {
      return;
    }
}

void swap(int i1, int i2) {
    Entry<K,V> tmp = this.entries.get(i1);
    this.entries.set(i1, this.entries.get(i2));
    this.entries.set(i2, tmp);
}

Тест:

#include "cutest/CuTest.h"
#include "heap.h"
#include <stdio.h>
#include <stdlib.h>

void TestAdd(CuTest *tc) {
  Heap* h = makeHeap(10);
  add(h, 4, "lol");
  CuAssertIntEquals(tc, 1, h->size);
  cleanupHeap(h);
}

CuSuite* StrUtilGetSuite() {
  CuSuite* suite = CuSuiteNew();
  SUITE_ADD_TEST(suite, TestAdd);
  return suite;
}

// Don't edit below this line

void RunAllTests(void) {
  CuString *output = CuStringNew();
  CuSuite* suite = CuSuiteNew();
  CuSuite* ourSuite = StrUtilGetSuite();

  CuSuiteAddSuite(suite, ourSuite);

  CuSuiteRun(suite);
  CuSuiteSummary(suite, output);
  CuSuiteDetails(suite, output);
  printf("%s\n", output->buffer);

  CuStringDelete(output);
  CuSuiteDelete(suite);
  free(ourSuite);
}

int main(void) {
  RunAllTests();
  return 0;
}

Answer 1

Перевод не достаточно близко .В Java у вас есть parent(index).В Си вы отметили это как (index-1)/2. Это то, что нужно использовать в качестве аргумента для других функций :

swap(h, index, (index-1)/2);
bubbleUp(h, (index-1)/2);