c - 为什么我的 Heapify That 看不起用 0 替换值（可能还有其他问题）

Question

我正在尝试做一个堆。它可以插入并检查其上方的值是否满足堆属性，但不检查其下方的值是否满足堆属性。出于某种原因，65 的值被其“左孩子”（数组外）替换为 0。我不知道为什么会发生这种情况。我一直在尝试调试这个大约一个小时。它可能还有一些我不知道的其他问题。这里的人似乎能够比我更好地调试东西，所以也许有人可以告诉我问题是什么？我什至不知道它在哪里交换价值。我可能需要在调试方面做得更好。

#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define SIZE 7

int heap[SIZE];
int fullness = 0;

int getParent(int element){
    //gets the parent of a given index in the heap array
    element -= 2;
    float toDivide = (float)element;
    toDivide /= 2;
    toDivide = ceil(toDivide);
    element = (int)toDivide;

    return element;
}

int getChild1(int element){
    //gets the left child of a given element in the heap list
    element *= 2;
    element += 1;
    return element;
}

int getChild2(int element){
    //gets the right child of a given element in the heap list
    element *= 2;
    element += 2;
    return element;
}

void swapWithChild1(int element){
    printf("\n");
    for(int i = 0; i < fullness; i++){
        //prints out the elements in the heap after min heapify
        printf("%d ", heap[i]);
    }
    printf("\n");
    printf("swapping: %d (left child): %d", heap[element], heap[getChild1(element)]);
    //swaps the chosen element in the heap with its left child
    int child1 = getChild1(element);
    int temp = heap[child1];
    heap[child1] = heap[element];
    heap[element] = temp;
}

void swapWithChild2(int element){
    printf("\n");
    for(int i = 0; i < fullness; i++){
        //prints out the elements in the heap after min heapify
        printf("%d ", heap[i]);
    }
    printf("\n");

    //swaps the chosen element in the heap with its right child
    int child2 = getChild2(element);
    int temp = heap[child2];
    heap[child2] = heap[element];
    heap[element] = temp;
}



void minHeapifyLookUp(int element){
    //restores the min heap property of the heap
    if(element == 0){
        return;
    }
    if(heap[element] < heap[getParent(element)]){
        //if the current element in the heap is less than its parent, swap them
        int temp = heap[element];
        heap[element] = heap[getParent(element)];
        heap[getParent(element)] = temp;
        minHeapifyLookUp(getParent(element));
    }
}

void child1AndChild2Heapify(int element){
    //if the left and right child both exist within the list
    bool leftChildLess = false;
    bool rightChildLess = false;
    if(heap[element] > heap[getChild1(element)]){
        //if the left child of the element is less than the element, set bool equal to true
        leftChildLess = true;
    }
    if(heap[element] > heap[getChild2(element)]){
       //if the right child of the element is less than the element, set bool equal to true
        rightChildLess = true;
    }
    if(leftChildLess && rightChildLess){
        if(heap[getChild1(element)] < heap[getChild2(element)]){
            printf("left child is less");
            //if the left child is less than the right child
            swapWithChild1(element);
        }
        else{
            //if the right child is less than or equal to the left child
            swapWithChild2(element);
        }
    }
    else if(leftChildLess){
        swapWithChild1(element);
    }
    else if(rightChildLess){
        swapWithChild2(element);
    }
}

void child1Heapify(int element){
    //if only the left child exists in the heap
    if(heap[element] > heap[getChild1(element)]){
        swapWithChild1(element);
    }
}

void insertToHeap(int insert){
    //inserts an element into the heap and incraments the fullenss varaible
    heap[fullness] = insert;
    fullness++;
    minHeapifyLookUp(fullness-1);
}

void heapifyLookDown(int element){
    //recurusivly checks going down if the heap fufils the min heap property
    printf("element: %d\n", element);
    bool child1Out = false;
    bool child2Out = false;
    if(getChild1(element) > fullness){
        //if the left child is outside the heap
        printf("greater than fullness: %d\n", heap[element]);
        child1Out = true;
        child2Out = true;
    }
    else if(getChild2(element) > fullness){
        //if the right child is outside the heap
        child2Out = true;
    }
    if(!child1Out && !child2Out){
        //if the left and right child are both within the heap
        child1AndChild2Heapify(element);
        //recusivly goes down the heap
        heapifyLookDown(getChild1(element));
        heapifyLookDown(getChild2(element));
    }
    else if(child1Out == false && child2Out){
        //if the right child is outisde the heap but the left child is not
        printf("\nchild 1 is not out and child 2 is out: %d\n", heap[element]);
        child1Heapify(element);
        heapifyLookDown(getChild1(element));
    }

}

void deleteNode( ){


}

int main()
{
    int numList[SIZE] = {400,-1,3,63,12,5,100};
    for(int i = 0; i < SIZE; i++){
        //inserts the elements in numList into the heap
        heap[i] = numList[i];
        fullness++;
    }
    heapifyLookDown(0);
    for(int i = 0; i < fullness; i++){
        //prints out the elements in the heap after min heapify
        printf("%d ", heap[i]);
    }
}

标签： cheap