Priority Queue printing the wrong element dequeue'd, even though it dequeue's correctly-CodePudding

I'm working on following a tutorial on implementing a Priority Queue in C, however when I display my Priority Queue (should sort by student ID from highest to lowest), it prints in a different order.

The actual output is:

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

The expected output is:

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

It seems like it's printing the wrong studentID when I am de'queing, even though the heap is updating.

Code:

#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);
}

CodePudding user response：

It seems like it's printing the wrong studentID when I am de'queing, even though the heap is updating.

The problem is that

Your priority queue is providing the actual storage for its elements; and
When you dequeue, you are both reporting out pointers to the storage and modifying the contents of the storage.

That is well illustrated by considering this line from your dequeue() function:

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

Note well that for any given value of pq, the expression &pq->studentPQ[0] always evaluates to the same pointer.

The function then modifies the data at the location to which that pointer points ...

    deleteRoot(pq, student);

... and returns the pointer. So yes, when you examine the data to which the pointer points, you see the item on top of the heap, not the one that was just removed.

A relatively contained and minimal fix would be to read out and return items by value instead of by address:

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

You will of course need to modify the calls to that function appropriately, too.

Note also that it is strange that your deleteRoot() function accepts an argument telling it which element to delete. Isn't it supposed to delete the root? At least, that's the only thing you use it for. You don't need to tell it which node is the root node. That's inherent in the structure of your heap.