src/priority_queue.c
// minheap: parent is lower than children
// todo: maybe we could resize down. but who cares really
parent is lower than children
todo: maybe we could resize down. but who cares really
parent is lower than children todo : maybe we could resize down . but who cares really
vec3i pq_pop(vec3i_priority_queue *pq) {
    vec3i ret = pq->elements[0].v;
    pq->elements[0] = pq->elements[--pq->num_items];
    int i = 0;
    while (1) {
        int left_child_idx = left_child(i);
        int right_child_idx = right_child(i);
        bool left_child_exists = left_child_idx < pq->num_items;
        bool right_child_exists = right_child_idx < pq->num_items;
        int lowest_child;
        if (!left_child_exists && !right_child_exists) break;
        if (left_child_exists && !right_child_exists) {
            lowest_child = left_child_idx;
        } else {
            float left_priority = pq->elements[left_child_idx].p;
            float right_priority = pq->elements[right_child_idx].p;
            if (left_priority < right_priority) {
                lowest_child = left_child_idx;
            } else {
                lowest_child = right_child_idx;
            }
        }
        vec3i_pq_posting tmp = pq->elements[i];
        pq->elements[i] = pq->elements[lowest_child];
        pq->elements[lowest_child] = tmp;
        i = lowest_child;
    }
    return ret;
}
vec3i pq_pop ( vec3i_priority_queue * pq ) { vec3i ret = pq -> elements [ 0 ] . v ; pq -> elements [ 0 ] = pq -> elements [ -- pq -> num_items ] ; int i = 0 ; while ( 1 ) { int left_child_idx = left_child ( i ) ; int right_child_idx = right_child ( i ) ; bool left_child_exists = left_child_idx < pq -> num_items ; bool right_child_exists = right_child_idx < pq -> num_items ; int lowest_child ; if ( ! left_child_exists && ! right_child_exists ) break ; if ( left_child_exists && ! right_child_exists ) { lowest_child = left_child_idx ; } else { float left_priority = pq -> elements [ left_child_idx ] . p ; float right_priority = pq -> elements [ right_child_idx ] . p ; if ( left_priority < right_priority ) { lowest_child = left_child_idx ; } else { lowest_child = right_child_idx ; } } vec3i_pq_posting tmp = pq -> elements [ i ] ; pq -> elements [ i ] = pq -> elements [ lowest_child ] ; pq -> elements [ lowest_child ] = tmp ; i = lowest_child ; } return ret ; }
minheap: parent is lower than children
todo: maybe we could resize down.
minheap : parent is lower than children todo : maybe we could resize down .
//printf("settin 0 to thing at %d\n", pq->num_items); //pq->num_items--; // downheap // now swap parent with lowest child