• one constructor, namely,
  • pq *create_pq(void)
    • that constructs a data structure of type pq, empty for the moment,
      and returns a pointer to it,
• two access functions, namely,
  
  • boolean pq_is_empty(pq *p)
    • that, given a pointer to a priority queue,
      returns TRUE if the priority queue is empty and returns FALSE otherwise,
  • pq_object *find_min(pq *p)
    
    • that, given a pointer to a nonempty priority queue,
      returns a pointer to an object in the priority queue that has the smallest cost,
• three manipulator functions, namely,
  
  • void insert(pq *p, pq_object *objectptr, cost object_cost);
    
    • that, given a pointer to a priority queue, given a pointer to an object, and given the cost of this object,
      inserts the object into the priority queue,
  • void delete_min(pq *p);
    
    • that, given a pointer to a nonempty priority queue,
      removes from the priority queue an object that has the smallest cost,
  • void reduce_cost(pq *p, pq_object *objectptr, cost smaller_cost);
    
    • that, given a pointer to a priority queue, given a pointer to an object in this priority queue, and given a cost value smaller_cost that is smaller than the current cost of the object, reduces the cost of the object to smaller_cost.

#define TRUE  1
#define FALSE 0
typedef char boolean;

Implementing Priority Queue as a linked list

typedef struct list_item
{
  pq_object *content;
  struct list_item *next;
} list_item;

typedef list_item pq;


pq *create_pq(void)
{
  pq *p;
  
  p = (pq *) malloc(sizeof(pq));
  if(p==NULL)    
    {
      printf("OUT OF MEMORY!\n");
      exit(1);
    }

  p->next=NULL;
  return p;
}

boolean pq_is_empty(pq *p)
{
  return( (p->next==NULL) ? TRUE : FALSE ); 
}

pq_object *find_min(pq *p)
{
  list_item *winner, *candidate;
  
  if(pq_is_empty(p)==TRUE)
    {
      printf("TRIED TO FIND A MIN-OBJECT IN AN EMPTY PRIORITY QUEUE!\n");
      exit(1);
    }

  winner=p->next;
  for(candidate=p->next->next; candidate; candidate=candidate->next)
    {
      if(candidate->content->pq_cost < winner->content->pq_cost)
        winner=candidate;
    }
  return winner->content;
}

void pq_insert(pq *p, pq_object *object, cost object_cost)
{
  list_item *new_item;
  
  new_item = (list_item *) malloc(sizeof(list_item));
  if(new_item==NULL)
    {
      printf("OUT OF MEMORY!\n");
      exit(1);
    }

  object->pq_cost=object_cost;
  new_item->content=object;

  new_item->next=p->next;
  p->next=new_item;
}

void delete_min(pq *p)
{
  list_item *winner, *candidate, *previous;
  
  if(pq_is_empty(p)==TRUE)
    {
      printf("TRIED TO FIND A MIN-OBJECT IN AN EMPTY PRIORITY QUEUE!\n");
      exit(1);
    }

  winner=p->next;
  for(candidate=p->next->next; candidate; candidate=candidate->next)
    {
      if(candidate->content->pq_cost < winner->content->pq_cost)
	winner=candidate;
    }
  for(previous=p; previous->next != winner; previous=previous->next);

  previous->next=winner->next;
  free(winner);
}

void reduce_cost(pq *p, pq_object *object, cost smaller_cost)
{
  object->pq_cost=smaller_cost;
}

Implementing Priority Queue as a binary heap

Implementing Priority Queue as a pairing heap

A pairing heap is an ordered tree of pointers to the objects; the tree is represented by a pair of pointers for each of its nodes,

• node.down that points to the leftmost child of node
  (and is NULL if and only if node is a leaf) and
• node.across that points to the immediate successor of node in the list of its siblings
  (and is NULL if and only if node is either the root of the tree or the rightmost child of its parent);

• node.content that point to objects in the priority queue

x.content->pq_cost <= y.content->pq_cost
whenever y is a child of x.

In the objects of the priority queue, we shall maintain elements pq_location that point to the tree nodes of the pairing heap and reverse the pointers content: if x points to a tree node, then

x->content->pq_location equals x

y->pq_location->content equals y.

pq *create_pq(void)
{
  pq *p;
  p = (pq *) malloc(sizeof(pq));
  if(p==NULL)    
    {
      printf("OUT OF MEMORY!\n");
      exit(1);
    }
      
  *p=NULL;
  return p;
}

The access function pq_is_empty, given a pointer p to a pointer *p to the root of a pairing heap, returns TRUE if the pairing heap is empty and returns FALSE otherwise; the access function find_min, given a pointer p to a pointer *p to the root of a nonempty pairing heap, returns a pointer to the object in the priority queue that the root of the pairing heap points to.

boolean pq_is_empty(pq *p)
{
  return( (*p==NULL) ? TRUE : FALSE ); 
}

pq_object *find_min(pq *p)
{
  if(pq_is_empty(p)==TRUE)
    {
      printf("TRIED TO FIND A MIN-OBJECT IN AN EMPTY PRIORITY QUEUE!\n");
      exit(1);
    }

  return (*p)->content;
}                

tree_node *link(tree_node *a, tree_node *b)
{
  if(a->content->pq_cost < b->content->pq_cost)
    {
      b->across=a->down;
      a->down=b;
      a->across=NULL;
      return a;
    }
  else
    {
      a->across=b->down;
      b->down=a;
      b->across=NULL;
      return b;
    }
}

void pq_insert(pq *p, pq_object *object, cost object_cost)
{
  tree_node *new_node;
  new_node = (tree_node *) malloc(sizeof(tree_node));
  if(new_node==NULL)
    {
      printf("OUT OF MEMORY!\n");
      exit(1);
    }
  new_node->content=object;
  new_node->down=NULL;
  new_node->across=NULL;

  object->pq_location=new_node;
  object->pq_cost=object_cost;

  *p = (pq_is_empty(p)==TRUE ? new_node : link(*p,new_node));
}

reduce_cost(p, object, smaller_cost)

object->pq_cost=smaller_cost;

1. the node object->pq_location that points to the object is removed from the list of its siblings and then
2. the subtree of the pairing heap that is rooted at object->pq_location is reinserted into the pairing heap
   by a sequence of operations much like pq_insert(p, object, smaller_cost) except that
   new_node->down is set at object->pq_location->down rather than at NULL.

object->pq_location->content=NULL;

void reduce_cost(pq *p, pq_object *object, cost smaller_cost)
{
  tree_node *new_node;

  object->pq_cost=smaller_cost;

  if(object->pq_location!=*p)
    {
      new_node = (tree_node *) malloc(sizeof(tree_node));
      if(new_node==NULL)
	{
	  printf("OUT OF MEMORY!\n");
	  exit(1);
	}
      new_node->content=object;
      new_node->down=object->pq_location->down;      
      new_node->across=NULL;

      object->pq_location->content=NULL;
      object->pq_location=new_node;      
      
      *p = link(*p,new_node);
    }
}

• returns the first meaningful child of the root in the sequence
  child, child->across, child->across->across, ...
  (having first removed all the preceding meaningless children in this sequence)

• returns NULL to signify that there is is no meaningful child of the root in the sequence
  child, child->across, child->across->across, ...
  (having first removed all the children in this sequence).

tree_node *find_sibling(tree_node *child)
{
  tree_node *memo;
  
  while(child && child->content==NULL)
    {
      memo=child, child=child->across;
      free(memo);
    }
  return child;
}

we pass through the list of (meaningful and meaningless) children of the root from left to right,
weeding out the meaningful children v₁ , v₂ , ..., v_k in the left-to-rught order;
as we do, we link v₁ with v₂ and record the root of the resulting pairing heap as w₁;
we link v₃ with v₄ and record the root of the resulting pairing heap as w₂; and so on.
If k=2j, then we end up with winners w₁ , w₂ , ..., w_j;
if k=2j-1, then we end up with winners w₁ , w₂ , ..., w_j-1 and set w_j=v_k.

we pass through the list of the j winners in the reverse order, from w_j to w₁,
linking first w_j and w_j-1, then the winner of this match and w_j-2, then the winner of this match and w_j-3, and so on.

void delete_min(pq *p)
{
  tree_node *a, *b, *memo;

  if(pq_is_empty(p)==TRUE)
    {
      printf("TRIED TO DELETE A MIN-OBJECT FROM AN EMPTY PRIORITY QUEUE!\n");
      exit(1);
    }

  a=find_sibling((*p)->down);
  (*p)->down = NULL;
  while(a)
    {
      b=find_sibling(a->across);
      if(b)
        {
          memo=find_sibling(b->across);
          a=link(a,b);
          a->across=(*p)->down, (*p)->down=a;
          a=memo;                                                              
        }
      else
        {
          a->across=(*p)->down, (*p)->down=a;
          break;
        }
    }

  if((*p)->down)
    {
      for(a=(*p)->down->across; a; a=memo)
        {
          memo=a->across;
          (*p)->down=link((*p)->down,a);
        }
    }

  memo=*p;
  *p=(*p)->down;
  free(memo);
}