Ошибка при вставке в кучу

Question

Ниже приведен код C++ для вставки в кучу. Значение k вставляется, но оно вставлено снизу. Я ожидал, что он будет изнашиваться с этим циклом while.

void Insert(heap1* myHeap, int k) 
{ 
    (myHeap->size)++; 
    int i = myHeap->size; 

    while (i > 1 && myHeap->H[i/2].key < k) 
    { 
     myHeap->H[i].key = myHeap->H[i/2].key; 
     i = i/2; 
    } 
    myHeap->H[i].key = k; 
} 

У меня есть heapify процедуры, что я пытался использовать для этого до этой попытки, что я знаю, работу в рамках других моих процедур кучи. Я просто не могу заставить его работать внутри Insert, поэтому я пошел с вышеуказанным маршрутом. Ниже heapify только в случае его полезного использования:

void heapify(heap1* myHeap, int i) 
{ 
    int l = 2 * i; 
    int r = 2 * i + 1; 
    int largest; 

    if (l <= myHeap->size && myHeap->H[l].key > myHeap->H[i].key) 
     largest = l; 
    else 
     largest = i; 
    if (r <= myHeap->size && myHeap->H[r].key > myHeap->H[largest].key) 
     largest = r; 
    if (largest != i) 
     { 
     myHeap->H[i].key = myHeap->H[i].key + myHeap->H[largest].key; 
     myHeap->H[largest].key = myHeap->H[i].key - myHeap->H[largest].key; 
     myHeap->H[i].key = myHeap->H[i].key - myHeap->H[largest].key; 
     heapify(myHeap, largest); 
    } 
} 

Если кто-то может привести меня в правильном направлении, о том, как получить его, чтобы восстановить свои свойства кучи, я бы в значительной степени оценить его.

Answer 1

попробуйте использовать этот код:

void insert(int heap[], int *n, int item){ 
    (*n)++; 
    heap[*n] = item; 
    reheapify_upward(heap, *n); 
} 

void reheapify_upward(int heap[],int start){ 
    int temp,parent; 
    if(start>1){ 
     parent=start/2; 
     if(heap[parent]<heap[start]){ 
      temp=heap[start]; 
      heap[start]=heap[parent]; 
      heap[parent]=temp; 
      reheapify_upward(heap,parent); 
     } 
    } 
}