Вставка элементов в очередь приоритетов с использованием кучи

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 одинаковы для 2 вызовов. Но r недействителен для первого звонка !. Он имеет случайные данные.

При звонке рекомендуем использовать min_heapify(int index, int size). Вызов наверху min_heapify(count, count); count++; Внутри min_heapify() вы можете использовать значенияи size, чтобы узнать, имеет ли parent (индекс/2) right (индекс <) или нет и обрабатывается соответствующим образом.