Function PQueueGetMax

OTHER/METIS/pqueue.c:441–506

* This function returns the vertex with the largest gain from a partition * and removes the node from the bucket list **************************************************************************/

* and removes the node from the bucket list
**************************************************************************/
int PQueueGetMax(PQueueType *queue)
{
  int vtx, i, j, gain, node;
  idxtype *locator;
  ListNodeType *tptr;
  KeyValueType *heap;

  if (queue->nnodes == 0)
    return -1;

  queue->nnodes--;

  if (queue->type == 1) {
    tptr = queue->buckets[queue->maxgain];
    queue->buckets[queue->maxgain] = tptr->next;
    if (tptr->next != NULL) {
      tptr->next->prev = NULL;
    }
    else {
      if (queue->nnodes == 0) {
        queue->maxgain = -queue->ngainspan;
      }
      else 
        for (; queue->buckets[queue->maxgain]==NULL; queue->maxgain--);
    }

    return tptr->id;
  }
  else {
    heap = queue->heap;
    locator = queue->locator;

    vtx = heap[0].val;
    locator[vtx] = -1;

    if ((i = queue->nnodes) > 0) {
      gain = heap[i].key;
      node = heap[i].val;
      i = 0;
      while ((j=2*i+1) < queue->nnodes) {
        if (heap[j].key > gain) {
          if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
            j = j+1;
          heap[i] = heap[j];
          locator[heap[i].val] = i;
          i = j;
        }
        else if (j+1 < queue->nnodes && heap[j+1].key > gain) {
          j = j+1;
          heap[i] = heap[j];
          locator[heap[i].val] = i;
          i = j;
        }
        else
          break;
      }

      heap[i].key = gain;