代码之家 › 专栏 › 技术社区 › mourinho

使用数组实现最小堆[关闭]

heap data-structures algorithm c

-2

mourinho · 技术社区 · 8 年前

我试图在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编译器),所以我陷入了这个问题。

谢谢你的帮助。

2 回复 | 直到 8 年前

Jorge Y. 8 年前

在heapifyUp中,您有 while(i) 陈述“i”被初始化为1,并且从未被修改。在这个循环中没有任何“返回”或“中断”。因此,这种情况永远保持不变。

Eziz Durdyyev 8 年前

您的代码有一些问题,以下是其中的几个问题:
正如Jorge提到的 heapifyUp() 函数永远不会上升,它只是停留在那里,进入无限循环。
2、英寸 heapifyDown() 函数有越界问题。您需要检查其子项是否有效。它有逻辑问题。
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;
}