使用数组实现最小堆

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（不支持代码块，从来没有真正理解如何使用 gdb，我只是在文本编辑器上使用内置的 gcc 编译器），所以我被困在这个问题上。

感谢您的帮助。

Answer 1

在 heapifyUp 中你有一个 while(i) 语句。 "i" 被初始化为 1 并且永远不会被修改。而且您在该循环内没有任何 "return" 或 "break" 。所以条件永远成立。

Answer 2

您的代码有一些问题，以下是其中的几个问题：
1. 正如 Jorge 提到的，在你的 heapifyUp() 函数中你永远不会上升，它只是停留在那里并进入无限循环。
2. 在 heapifyDown() 函数中你有越界问题。您需要检查其 children 是否有效。而且逻辑有问题
3. 另外，请决定是使用 0 索引数组还是 1 索引数组。因为你的一些函数认为它是 0 索引而有些认为它是 1 索引。我根据 1 个索引数组进行了更正。如果您愿意，我可以将其更改为 0 索引，或者这可能是您的作业。

已经尽力了，还有一些地方需要修改：

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

#define max 100

int heap[max];
int size = 0;

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

    while(1){ // 
        int parent = i/2;
        if (parent > 0 && heap[parent] > heap[i]){
            int t = heap[parent];
            heap[parent] = heap[i];
            heap[i]=t;
            i = parent;
        } else {
            break;
        }
    }
}

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

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

        if(heap[i] >= heap[t]) break;

        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[1];
}

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

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

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

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

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

    printHeap();
    printf("%d\n",deleteMin());
    return 0;
}

使用数组实现最小堆

Implementing min Heap using an array

c

algorithm

heap

data-structures