Возникают проблемы при вставке значений в максимальную двоичную кучу

Question

Я создал двоичную кучу с помощью C. Вот функции для инициализации кучи и вставки значений

int *heapArray; // pointer to array of elements in heap
int capacity = 0; // maximum possible size of min heap, initially set to 0
int heap_size; // Current number of elements in min heap
int d = 2;  //max number of children per node

int getParent(int i) //get the parent index of i
{
    return (i/d);
}

bool isFull() //check if heap is full
{
    if(heap_size == capacity)
        return true;
    if(heap_size < capacity)
        return false;
}

void initializeHeap(int cap) //initialize the heap
{
    heap_size = 0;
    capacity = cap;
    heapArray = (int*)malloc(cap*sizeof(int));
}

void insertValue(int x) //insert a value into the heap
{
    if(isFull()) //If heap is already full, double the heap size
    {
        capacity = 2*capacity;
        heapArray = realloc(heapArray,capacity*sizeof(int));
    }

    heap_size = heap_size + 1;
    heapArray[heap_size] = x; //insert new value into heap (not zero-indexed)
    maxHeapSwim(heap_size);
}

void maxHeapSwim(int k) //move value up the heap to maintain max-heap order
{
    while(k > 1 && heapArray[getParent(k)] < heapArray[k])
    {
        swap(&heapArray[k],&heapArray[parent(k)]);
        k = parent(k);
    }
}

Затем в методе main () я попытался вставить значения в кучу и распечататьиз значений:

int main()
{

  initializeHeap(1); //Set the heap capacity to 1

  insertValue(2);
  insertValue(3);
  insertValue(1);
  insertValue(6);
  insertValue(4);

  printf("\n");
  printf("%i", heapArray[1]);
  printf("\n");
  printf("%i", heapArray[2]);
  printf("\n");
  printf("%i", heapArray[3]);
  printf("\n");
  printf("%i", heapArray[4]);
  printf("\n");
  printf("%i", heapArray[5]);
  printf("\n");

  return 0;

}

Поскольку это максимальная куча, я надеялся, что результат будет выглядеть следующим образом:

6
4
1
2
3

Но вместо этого он выглядел так:

6
4
1
0
3

Я не понимаю.Почему 2 превращается в 0?У меня такое ощущение, что это как-то связано с тем, как я удваиваю размер кучи в функции insertValue () .... возможно, так, как я использую realloc.Есть что-то, что я делаю неправильно?

Еще одна вещь, на которую стоит обратить внимание, это то, что моя двоичная куча не индексируется нулями.Первое значение вставляется в heapArray [1], второе значение в heapArray [2] и так далее.

Answer 1

Это сработало для меня:

void insertValue(int x)
{
    if(capacity < 10)
    {
        capacity = 10;
        heapArray = (int*)realloc(heapArray,capacity*sizeof(int));
    }
    if(heap_size >= capacity/2)
    {
        capacity += 10;
        heapArray = (int*)realloc(heapArray,capacity*sizeof(int));
    }

    heap_size = heap_size + 1;
    heapArray[heap_size] = x;
    maxHeapSwim(heap_size);
}

Ключ должен гарантировать, что двоичная куча никогда не будет заполнена.

Answer 2

Некоторые изменения в первом разделе вашего кода работают для меня.

Реализация swap() и некоторые незначительные изменения.

Код

#define false 0
#define true 1

int *heapArray; // pointer to array of elements in heap
int capacity = 0; // maximum possible size of min heap, initially set to 0
int heap_size; // Current number of elements in min heap
int d = 2;  //max number of children per node

int getParent(int i) //get the parent index of i
{
    return (i/d);
}

void maxHeapSwim(int k) //move value up the heap to maintain max-heap order
{
    while(k > 1 && heapArray[getParent(k)] < heapArray[k])
    {
        //swap(&heapArray[k],&heapArray[parent(k)]);
        int x=heapArray[k];
        heapArray[k]=heapArray[getParent(k)];
        heapArray[getParent(k)]=x;
        k = getParent(k);
    }
}

int  isFull() //check if heap is full
{
    if(heap_size == capacity)
        return true;
    if(heap_size < capacity)
        return false;
}

void initializeHeap(int cap) //initialize the heap
{
    heap_size = 0;
    capacity = cap;
    heapArray = (int*)malloc(cap*sizeof(int));
}

void insertValue(int x) //insert a value into the heap
{
    if(isFull()) //If heap is already full, double the heap size
    {
        capacity = 2*capacity;
        heapArray = realloc(heapArray,capacity*sizeof(int));
    }

    heap_size = heap_size + 1;
    heapArray[heap_size] = x; //insert new value into heap (not zero-indexed)
    maxHeapSwim(heap_size);
}




int main()
{  

  initializeHeap(1); //Set the heap capacity to 1

  insertValue(2);
  insertValue(3);
  insertValue(1);
  insertValue(6);
  insertValue(4);

  printf("\n");
  printf("%i", heapArray[1]);
  printf("\n");
  printf("%i", heapArray[2]);
  printf("\n");
  printf("%i", heapArray[3]);
  printf("\n");
  printf("%i", heapArray[4]);
  printf("\n");
  printf("%i", heapArray[5]);
  printf("\n");

  return 0;
}

выход

./code 


6
4
1
2
3