This file contains (part of) the code from "Algorithms in C, Third Edition,
Parts 1-4," by Robert Sedgewick, and is covered under the copyright
and warranty notices in that book. Permission is granted for this
code to be used for educational purposes in association with the text,
and for other uses not covered by copyright laws, provided that
the following notice is included with the code:

 	"This code is from "Algorithms in C, Third Edition,"
	by Robert Sedgewick, Addison Wesley Longman, 1998."

Commercial uses of this code require the explicit written
permission of the publisher. Send your request for permission,
stating clearly what code you would like to use, and in what
specific way, to: aw.cse@aw.com

CHAPTER 9. Priority Queues and Heapsort
-----
void PQinit(int);
 int PQempty();
void PQinsert(Item);
Item PQdelmax();
-----
#include <stdlib.h>
#include "Item.h"   
static Item *pq; 
static int N;
void PQinit(int maxN)
  { pq = malloc(maxN*sizeof(Item)); N = 0; }
 int PQempty() 
  { return N == 0; }
void PQinsert(Item v)
  { pq[N++] = v; }
Item PQdelmax()
  { int j, max = 0;
    for (j = 1; j < N; j++)
      if (less(pq[max], pq[j])) max = j;
    exch(pq[max], pq[N-1]);  
    return pq[--N];
  }
-----
fixUp(Item a[], int k)
  {
    while (k > 1 && less(a[k/2], a[k]))
      { exch(a[k], a[k/2]); k = k/2; }
  }
-----
fixDown(Item a[], int k, int N)
  { int j;
    while (2*k <= N)
      { j = 2*k;
        if (j < N && less(a[j], a[j+1])) j++;
        if (!less(a[k], a[j])) break;
        exch(a[k], a[j]); k = j;
      }
  }
-----
#include <stdlib.h>
#include "Item.h"   
static Item *pq; 
static int N;
void PQinit(int maxN)
  { pq = malloc((maxN+1)*sizeof(Item)); N = 0; }
 int PQempty() 
  { return N == 0; }
void PQinsert(Item v)
  { pq[++N] = v; fixUp(pq, N); }
Item PQdelmax()
  { 
    exch(pq[1], pq[N]); 
    fixDown(pq, 1, N-1); 
    return pq[N--]; 
  }
-----
void PQsort(Item a[], int l, int r)
  { int k;
    PQinit();
    for (k = l; k <= r; k++) PQinsert(a[k]);
    for (k = r; k >= l; k--) a[k] = PQdelmax();
  }
-----
#define pq(A) a[l-1+A]
void heapsort(Item a[], int l, int r)
  { int k, N = r-l+1;
    for (k = N/2; k >= 1; k--) 
      fixDown(&pq(0), k, N);
    while (N > 1) 
      { exch(pq(1), pq(N)); 
        fixDown(&pq(0), 1, --N); }
  }
-----
typedef struct pq* PQ;
typedef struct PQnode* PQlink;
    PQ PQinit();
   int PQempty(PQ);
PQlink PQinsert(PQ, Item);
  Item PQdelmax(PQ);
  void PQchange(PQ, PQlink, Item);
  void PQdelete(PQ, PQlink);
  void PQjoin(PQ, PQ);
-----
#include <stdlib.h>
#include "Item.h"
#include "PQfull.h"
struct PQnode { Item key; PQlink prev, next; };
struct pq { PQlink head, tail; };
PQ PQinit()
  { PQ pq = malloc(sizeof *pq);
    PQlink h = malloc(sizeof *h),
           t = malloc(sizeof *t);
    h->prev = t; h->next = t;
    t->prev = h; t->next = h;
    pq->head = h; pq->tail = t;
    return pq;
  }
int PQempty(PQ pq)
  { return pq->head->next->next == pq->head; }
PQlink PQinsert(PQ pq, Item v)
  { PQlink t = malloc(sizeof *t);
    t->key = v; 
    t->next = pq->head->next; t->next->prev = t;
    t->prev = pq->head; pq->head->next = t;
  }
Item PQdelmax(PQ pq)
  { Item max; struct PQnode *t, *x = pq->head->next;
    for (t = x; t->next != pq->head; t = t->next)
      if (t->key > x->key) x = t;
    max = x->key; 
    x->next->prev = x->prev; 
    x->prev->next = x->next; 
    free(x); return max;
  }
-----
void PQchange(PQ pq, PQlink x, Item v)
  { x->key = v; }  
void PQdelete(PQ pq, PQlink x)
  { PQlink t;
    t->next->prev = t->prev;
    t->prev->next = t->next;
    free(t);
  }  
void PQjoin(PQ a, PQ b)
  { PQlink atail, bhead;
    a->tail->prev->next = b->head->next;
    b->head->next->prev = a->tail->prev;
    a->head->prev = b->tail; 
    b->tail->next = a->head;
    free(a->tail); free(b->head);
  }
-----
 int less(int, int);
void PQinit();
 int PQempty();
void PQinsert(int);
 int PQdelmax();
void PQchange(int);
void PQdelete(int);
-----
#include "PQindex.h"
typedef int Item;
static int N, pq[maxPQ+1], qp[maxPQ+1];
void exch(int i, int j)
  { int t;
    t = i; i = j; j = t;
    t = qp[i]; qp[i] = qp[j]; qp[j] = t;
  }
void PQinit() { N = 0; }
 int PQempty() { return !N; }
void PQinsert(int k)
  { qp[k] = ++N; pq[N] = k; fixUp(pq, N); }
 int PQdelmax()
  { 
    exch(pq[1], pq[N]); 
    fixDown(pq, 1, --N); 
    return pq[N+1]; 
  }
void PQchange(int k)
  { fixUp(pq, qp[k]); fixDown(pq, qp[k], N); }
-----
PQlink pair(PQlink p, PQlink q)
  { PQlink t;
    if (less(p->key, q->key)) 
         { p->r = q->l; q->l = p; return q; }
    else { q->r = p->l; p->l = q; return p; }
  }
-----
PQlink PQinsert(PQ pq, Item v)
  { int i;
    PQlink c, t = malloc(sizeof *t);
    c = t; c->l = z; c->r = z; c->key = v;
    for (i = 0; i < maxBQsize; i++)
      {
        if (c == z) break;
        if (pq->bq[i] == z) { pq->bq[i] = c; break; }
        c = pair(c, pq->bq[i]); pq->bq[i] = z;
      }
    return t;
  }
-----
Item PQdelmax(PQ pq)
  { int i, j, max; PQlink x; Item v; 
    PQlink temp[maxBQsize];
    for (i = 0, max = -1; i < maxBQsize; i++)
      if (pq->bq[i] != z) 
        if ((max == -1) || (pq->bq[i]->key > v))
          { max = i; v = pq->bq[max]->key; }
    x = pq->bq[max]->l; 
    for (i = max; i < maxBQsize; i++) temp[i] = z; 
    for (i = max ; i > 0; i--)
      { temp[i-1] = x; x = x->r; temp[i-1]->r = z; }
    free(pq->bq[max]); pq->bq[max] = z;
    BQjoin(pq->bq, temp);  
    return v;
  }      
-----
#define test(C, B, A) 4*(C) + 2*(B) + 1*(A)
void BQjoin(PQlink *a, PQlink *b)
  { int i; PQlink c = z;
    for (i = 0; i < maxBQsize; i++)
      switch(test(c != z, b[i] != z, a[i] != z))
        {
          case 2: a[i] = b[i]; break;
          case 3: c = pair(a[i], b[i]); 
                  a[i] = z; break;
          case 4: a[i] = c; c = z; break;
          case 5: c = pair(c, a[i]); 
                  a[i] = z; break;
          case 6: 
          case 7: c = pair(c, b[i]); break;
        }
  }
void PQjoin(PQ a, PQ b)
  { BQjoin(a->bq, b->bq); }

----------