A question about priority queues

[seonwee]

Hello, I saw in your code that you treat the position of index 1 as the top of the heap element, and in the function named solve, you have a comment that says heap[0] position is not used, so before you put the first element in the priority queue, you should put an occupancy number into the heap, such as 0, Otherwise, when the first element is put into the priority queue, the index of the element is 0 instead of 1. Here is the code that I think needs to be changed:

bool heap_empty() {
    return heap.size() == 1;//there is a placeholder element when the heap is empty.
}

bool solve() {
    //...
    heap.push_back(0);//add a placeholder element
    heap.reserve(N + 1); // heap[0] is not used
    heap_index.resize(N + 1);
    for (uint v = 1; v <= N; ++v)
        heap_push(v);
   //...

[nyuichi]

Aw sorry I didn’t notice. What you pointed out seems correct. I am going to make a patch when I have time.