c - 使用数组实现最小堆

Question

我正在尝试用 C 实现最小堆。

// Heaps:
// node i -> 2i and 2i+1 children
// 2i//2 = i and 2i+1//2 = i same parents

#include <stdio.h>
#include <stdlib.h>

#define max 100

int heap[max];
int size = 0;

void heapifyUp(){ // last element
    int i = size;

    while(i){ // 
        int parent = i/2;
        if (heap[parent]<heap[i]){
            int t = heap[parent];
            heap[parent] = heap[i];
            heap[i]=t;
        }        
    }
}

void heapifyDown(){ // top element
    int i = 0;

    while(i<=size){
        int c1 = 2*i;
        int c2 = 2*i + 1;
        int t = 0;
        if (heap[c1]>=heap[c2]){
            t = c2;
        }
        else{
            t = c1;
        }
        int temp = heap[i];
        heap[i] = heap[t];
        heap[t] = temp;
        i = t;
    }
}

void insert(int key){
    size = size + 1;
    heap[size] = key;
    heapifyUp();
}

int returnMin(){
    return heap[0];
}

int deleteMin(){
    int t = heap[0];
    heap[0] = heap[size];
    size = size - 1;
    heapifyDown();
    return t;
}

void printHeap(){

    int i = 0;
    while(i<=size){
        printf("%d",heap[i]);
        i = i + 1;
    }
}

int main(){
    insert(10);
    insert(20);
    insert(11);
    insert(7);
    insert(18);

    printHeap();
    printf("%d",deleteMin());

    insert(110);
    insert(-7);
    insert(15);

    printf("%d",deleteMin());
}

问题是，当我运行程序时，我没有得到任何输出，并且程序不会终止。

我认为我已经正确实现了逻辑。

使用 C 调试器很难，就像我在 Mac 上一样(不支持 Codeblocks，从来没有真正理解如何使用 gdb，我只是在文本编辑器上使用内置的 gcc 编译器)，所以我陷入了困境这个问题。

感谢您的帮助。

Answer 1

在 heapifyUp 中，有一个 while(i) 语句。 “i” 被初始化为 1 并且永远不会被修改。并且该循环内没有任何“返回”或“中断”。所以这个条件永远成立。