c - 使用堆将元素插入优先级队列

Question

我想将元素插入优先级队列中，以便对它们进行排序，但我没有正确使用 min_heapify 函数。到目前为止，这是我的代码:-

#include <stdio.h>
#include <stdlib.h>
struct entity{ //An entity consists has its data and its priority
    int data; 
    int priority;
};
void swap(int *a ,int *b){
    int temp = *a; *a = *b; *b = temp;
}
void min_heapify(struct entity a[], int p){
    int r = (p+1)*2, l=r-1, smallest = p; //p is parent, r is right child and l is left child
    if(l < p && a[l].priority < a[p].priority) smallest = l;
    if(r < p && a[r].priority < a[smallest].priority) smallest = r;
    if(smallest != p){
        swap(&a[p].data, &a[smallest].data); //swap child and parent if parent isn't the smallest
        swap(&a[p].priority, &a[smallest].priority);
        min_heapify(a, smallest); //Keep on calling same method until parent is the smallest
    }
}
void display(struct entity a[], int count){
    printf("The Queue is:-\n");
    if(count == 0) printf("Empty.");
    else for(int i = 0; i < count; i++)
        printf("\n%d\t(priority: %d)\n", a[i].data, a[i].priority);
}
int main(){
    int n, count = 0, choice;
    printf("Enter the size of the priority queue: ");
    scanf("%d", &n);
    struct entity *a = (struct entity*)malloc(sizeof(struct entity) * n);
    while(1){
        display(a, count);
        printf("1.Insert 2.Exit: ");
        scanf("%d", &choice);
        switch(choice){
            case 1: if(count < n){
                        printf("\nEnter the number and its priority:-\n");
                        scanf("%d%d", &a[count].data, &a[count].priority);
                        min_heapify(a, (++count)/2);
                    }break;
            case 2: return 0;
        }
    }
}

Answer 1

您的*a未初始化，因此包含随机数据。在 min_heapify() 中，您连续两次传递同一个父级。因此，两次调用的 l 和 r 是相同的。但是 r 对于第一次调用无效!它有随机数据。

调用时建议使用min_heapify(int index, int size)。顶部调用min_heapify(count, count); count++; 在 min_heapify() 中，您可以使用 index 和 size 值来了解是否有 parent (index/2)是否有正确(索引<大小)并进行相应处理。