优先级队列打印错误的元素脱队列，即使它正确地脱队列

Question

我正在学习在C中实现优先级队列的教程，但是当我显示优先级队列(应该按照学生ID从最高到最低排序)时，它会以不同的顺序打印。

实际产出如下：

Original Array: 4 2 6 1 5 3 7 
Dequeued student: 2
Min-Heap array: 2 5 6 1 7 3 
Dequeued student: 5
Min-Heap array: 5 1 6 3 7 
Dequeued student: 6
Min-Heap array: 6 1 7 3 
Min-Heap array: 6 1 7 3  

预期产出如下：

Original Array: 4 2 6 1 5 3 7 
Dequeued student: 4 <--
Min-Heap array: 2 5 6 1 7 3 
Dequeued student: 2 <--
Min-Heap array: 5 1 6 3 7 
Dequeued student: 5 <--
Min-Heap array: 6 1 7 3 
Min-Heap array: 6 1 7 3 

尽管堆正在更新，但当我正在执行任务时，它似乎打印错了studentID。

代码：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

struct Student;
struct PriorityQueue;


void swap(struct Student *a, struct Student *b);
void heapify(struct PriorityQueue *pq, int size, int i);
void insert(struct PriorityQueue *pq, struct Student *newStudent);
void deleteRoot(struct PriorityQueue *pq, struct Student *removeStudent);
void printArray(struct PriorityQueue *pq, int size);
struct Student *peek(struct PriorityQueue *pq);



struct Student {
    int studentID;
    int grade;
};

struct PriorityQueue {
    struct Student studentPQ[100];
    int size;
};


void swap(struct Student *a, struct Student *b) {
  struct Student temp = *b;
  *b = *a;
  *a = temp;
}

// Function to heapify the tree
void heapify(struct PriorityQueue *pq, int size, int i) {
  if (size == 1) {
  } else {
    // Find the lowest grade and swap it with the root. If there are two studentes with the same grade, swap the one with the lowest studentID.
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < size && pq->studentPQ[left].grade < pq->studentPQ[smallest].grade) {
      smallest = left;
    } else if (left < size && pq->studentPQ[left].grade == pq->studentPQ[smallest].grade) {
      if (pq->studentPQ[left].studentID < pq->studentPQ[smallest].studentID) {
        smallest = left;
      }
    }

    if (right < size && pq->studentPQ[right].grade < pq->studentPQ[smallest].grade) {
      smallest = right;
    } else if (right < size && pq->studentPQ[right].grade == pq->studentPQ[smallest].grade) {
      if (pq->studentPQ[right].studentID < pq->studentPQ[smallest].studentID) {
        smallest = right;
      }
    }

    // Swap and continue heapifying if root is not largest
    if (smallest != i) {
      swap(&pq->studentPQ[i], &pq->studentPQ[smallest]);
      heapify(pq, size, smallest);
    }
  }
}

// Function to insert an element into the tree
void insert(struct PriorityQueue *pq, struct Student *newStudent) {
  if (pq->size == 0) {
    pq->studentPQ[0] = *newStudent;
    pq->size += 1;
  } else {
    pq->studentPQ[pq->size] = *newStudent;
    pq->size += 1;
    for (int i = pq->size / 2 - 1; i >= 0; i--) {
      heapify(pq, pq->size, i);
    }
  }

}

// Function to delete an element from the tree
void deleteRoot(struct PriorityQueue *pq, struct Student *removeStudent) {
  int i;
  for (i = 0; i < pq->size; i++) {
    if (removeStudent->studentID == pq->studentPQ[i].studentID)
      break;
  }

  swap(&pq->studentPQ[i], &pq->studentPQ[pq->size - 1]);
  pq->size -= 1;
  for (int i = pq->size / 2 - 1; i >= 0; i--) {
    heapify(pq, pq->size, i);
  }
}

// Print the array
void printArray(struct PriorityQueue *pq, int size) {
  for (int i = 0; i < pq->size; ++i)
    printf("%d ", pq->studentPQ[i].studentID);
  printf("\n");
}

// peek the highest priority student
struct Student *peek(struct PriorityQueue *pq) {
  return &pq->studentPQ[0];
}

// dequeue the highest priority student
struct Student *dequeue(struct PriorityQueue *pq) {
  struct Student *student = &pq->studentPQ[0];
  deleteRoot(pq, student);
  return student;
}

// Driver code
int main() {
  struct PriorityQueue *pq = (struct PriorityQueue *)malloc(sizeof(struct PriorityQueue));
  pq->size = 0;
    struct Student student1 = {1, 8};
    struct Student student2 = {2, 2};
    struct Student student3 = {3, 9};
    struct Student student4 = {4, 0};
    struct Student student5 = {5, 5};
    struct Student student6 = {6, 6};
    struct Student student7 = {7, 8};


    insert(pq, &student1);
    insert(pq, &student2);
    insert(pq, &student3);
    insert(pq, &student4);
    insert(pq, &student5);
    insert(pq, &student6);
    insert(pq, &student7);

    struct Student *dequeueStudent = dequeue(pq);
    printf("Dequeued Student: %d\n", dequeueStudent->studentID);
    printf("Min-Heap array: ");
    printArray(pq, pq->size);
    
    *dequeueStudent = *dequeue(pq);
    printf("Dequeued Student: %d\n", dequeueStudent->studentID);
    printf("Min-Heap array: ");
    printArray(pq, pq->size);

    *dequeueStudent = *dequeue(pq);
    printf("Dequeued Student: %d\n", dequeueStudent->studentID);
    printf("Min-Heap array: ");
    printArray(pq, pq->size);

  printf("Min-Heap array: ");
    printArray(pq, pq->size);
}

Answer 1

--尽管堆正在更新，但当我正在执行任务时，它似乎打印了错误的studentID。

问题是

1. 您的优先级队列为其元素提供了实际的存储空间；以及

1. 当您排出队列时，您既报告了指向存储的指针，又修改了存储的内容.

考虑dequeue()函数中的这一行很好地说明了这一点：

struct Student \*student = &pq->studentPQ[0];

请注意，对于给定的pq值，表达式总是计算为相同的指针。

该函数然后在指针指向的位置修改数据.

deleteRoot(pq, student);

..。并返回指针。因此，是的，当您检查指针指向的数据时，您会看到堆顶部的项，而不是刚刚移除的项。

一个相对包含和最小的解决方法是按值而不是按地址读取和返回项目：

// dequeue the highest priority student
struct Student dequeue(struct PriorityQueue *pq) {
  struct Student student = pq->studentPQ[0];
  deleteRoot(pq, &student);
  return student;
}

当然，您也需要适当地修改对该函数的调用。

还请注意，奇怪的是，您的deleteRoot()函数接受一个参数，告诉它要删除哪个元素。不是应该删除根目录吗？至少，这是你唯一用的东西。您不需要告诉它哪个节点是根节点。这是堆结构中固有的。