C语言二叉堆实现优先队列：同优先级按ID排序问题求助

Hey! Let's dig into why your priority queue isn't handling equal priorities correctly. The core issue lies in how you're comparing nodes during insertion and heapification—your current logic splits priority and ID checks into separate steps, which breaks the proper heap order for equal-priority elements. Let's fix this step by step.

1. Insertion Logic Flaw #

Your insertkey uses two separate while loops: first for priority, then for ID when priorities are equal. This is wrong because:

• You reset i to heapsize-1 after the first loop, so you're re-checking from the bottom instead of continuing the upward adjustment from where you left off.
• You should combine both conditions into a single loop that checks if the current node is "better" than its parent (higher priority, or same priority with smaller ID) in one go.

2. MaxHeapify Comparison Errors #

Your maxheapify has two critical issues:

• You use <= heapsize for child index checks, but since heap elements are indexed from 0 to heapsize-1, this leads to out-of-bounds access. It should be < heapsize.
• The logic for selecting the "largest" (most optimal) node is fragmented. When comparing right child to the current largest, you first set largest = r if priorities are equal, then try to correct it—but this leads to wrong selections when the right child has the same priority but a larger ID.

Fixed Code #

Here's the revised code with all issues addressed:

#include <stdio.h>
#define SIZE 99999
int heapsize = 0;
int count = 0;
struct pqueue {
    int priority;
    int id;
};
struct pqueue A[SIZE];

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

void initializearray() {
    for(int i=0; i<SIZE; i++) {
        A[i].priority = 0;
        A[i].id = 0;
    }
}

int left(int i) {
    return (i * 2) + 1;
}

int right(int i) {
    return (i * 2) + 2;
}

int parent(int i) {
    return ((i - 1) / 2);
}

void insertkey(int z) {
    heapsize++;
    int i = heapsize - 1;
    A[i].priority = z;
    count++;
    A[i].id = count;

    // Single loop to handle both priority and ID checks
    while (i != 0) {
        int p_idx = parent(i);
        struct pqueue *parent_node = &A[p_idx];
        struct pqueue *curr_node = &A[i];

        // Check if current node is better than parent: higher priority, or same priority with smaller ID
        if (parent_node->priority < curr_node->priority || 
            (parent_node->priority == curr_node->priority && parent_node->id > curr_node->id)) {
            swap(&parent_node->priority, &curr_node->priority);
            swap(&parent_node->id, &curr_node->id);
            i = p_idx;
        } else {
            break;
        }
    }
}

void maxheapify(int i) {
    int l = left(i);
    int r = right(i);
    int largest = i;

    // Compare left child with current largest
    if (l < heapsize) {
        if (A[l].priority > A[largest].priority || 
            (A[l].priority == A[largest].priority && A[l].id < A[largest].id)) {
            largest = l;
        }
    }

    // Compare right child with current largest
    if (r < heapsize) {
        if (A[r].priority > A[largest].priority || 
            (A[r].priority == A[largest].priority && A[r].id < A[largest].id)) {
            largest = r;
        }
    }

    if (largest != i) {
        swap(&A[i].priority, &A[largest].priority);
        swap(&A[i].id, &A[largest].id);
        maxheapify(largest);
    }
}

int extractmax() {
    if (heapsize == 0) {
        return 0; // Indicate empty heap
    }
    int max_id = A[0].id;
    // Replace root with last element
    A[0] = A[heapsize - 1];
    heapsize--;
    maxheapify(0);
    return max_id;
}

int main() {
    int n;
    int z;
    initializearray();
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d", &z);
        if(z != 0) {
            insertkey(z);
        } else {
            int local = extractmax();
            if(local != 0) {
                printf("%d ", local);
            }
        }
    }
    printf("\n");
    return 0;
}

Testing the Fixed Code #

For your Test Case 2:

• Input: 10 1 1 1 1 2 0 0 0 0 0
• The code will first insert 5 elements: (priority 1, ID1), (1, ID2), (1, ID3), (1, ID4), (2, ID5). The heap will have ID5 as root (highest priority 2).
• When extracting:
  1. First extract returns ID5 (priority 2)
  2. Next extracts will pull the smallest ID from the priority 1 group: ID1, ID2, ID3, ID4
• Output: 5 1 2 3 4 which matches your expected result.

Key Takeaways #

• Always define a clear "comparator" logic for your priority queue: what makes one node better than another? For your case, it's (higher priority) || (same priority && smaller ID).
• Use this comparator consistently in both insertion (up-heap) and heapification (down-heap) steps.
• Be careful with array bounds: heap indices go from 0 to heapsize-1, so child checks should use < heapsize.

内容的提问来源于stack exchange，提问作者Coolerini