// index-heap-based priority queue.  heap routines are
// from "Algorithms in C, Third Edition", and
// "Algorithms in Java, Third Edition", Robert Sedgewick

// Summer 2016, changed for CLRS, 3rd ed., but still non-recursive.

// This is a prototype for demonstration purposes only.

#include <stdio.h>
#include <stdlib.h>

typedef int Item;

int N,          // Number of items in queue
    *pq,        // Priority queue
    *qp,        // Table of handles (for tracking)
    maxQueued;  // Capacity of priority queue
int *a;

int parent(int i)
{
  return i/2;
}

int left(int i)
{
  return 2*i;
}

int right(int i)
{
  return 2*i+1;
}

void exch(int i, int j)
{ 
// Swaps parent with child in heap
int t;

t = pq[i]; 
pq[i] = pq[j]; 
pq[j] = t;
qp[pq[i]] = i;
qp[pq[j]] = j;
}

void maxHeapInit(int *items,int n,int m)
{ 
int i;

a = items;    // Save reference to index table
maxQueued=m;
N = 0; 
pq=(int*) malloc((maxQueued+1)*sizeof(int)); // Contains subscripts to a[]
if (!pq)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
qp=(int*) malloc(n*sizeof(int));   // Inverse of pq, allows changing priorities
if (!qp)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
// Set all handles to unused
for (i=0;i<n;i++)
  qp[i]=(-1);
}

int maxHeapEmpty()
{ 
return !N; 
}

int maxHeapFull()
{ 
return N == maxQueued; 
}

int less(int i, int j)
{ 
// Notice how heap entries reference a[]
return a[pq[i]] < a[pq[j]]; 
}

void heapIncreaseKey(int *pq,int k) // AKA swim
{
while (k > 1 && less(parent(k), k))
{
  exch(k, parent(k));
  k = parent(k);
}
}

void maxHeapify(int *pq,int k, int N) // AKA sink
{
int j;

while (left(k) <= N)
{
  j = left(k);
  if (j < N && less(j, j+1))
    j=right(k);
  if (!less(k, j))
    break;
  exch(k, j);
  k = j;
}
}

void maxHeapInsert(int k)
{ 
qp[k] = ++N; 
pq[N] = k; 
heapIncreaseKey(pq, N); 
}

int heapExtractMax()
{ 
exch(1, N); 
maxHeapify(pq, 1, --N); 
qp[pq[N+1]]=(-1);  // Set to unused
return pq[N+1]; 
}

void maxHeapChange(int k)
{ // To be called when priority[k] has changed.
heapIncreaseKey(pq, qp[k]); 
maxHeapify(pq, qp[k], N); 
}

// Test driver for index-heap-based priority queue.
// Index is just a table of priorities whose
// subscripts are used in the PQ.

int main()
{
int n,m,op,i,val;
int *priority;

printf("Enter table (dictionary) size\n");
scanf("%d",&n);
if (n<1)
{
  printf("Illegal size %d\n",__LINE__);
  exit(0);
}
priority=(int*) malloc(n*sizeof(int));
if (!priority)
{
  printf("malloc failed for table %d\n",__LINE__);
  exit(0);
}
printf("Your table has keys %d through %d\n",0,n-1);
printf("Enter PQ (binary heap) size\n");
scanf("%d",&m);

maxHeapInit(priority,n,m);

for (i=0;i<n;i++)
  priority[i]=(-1);

while (1)
{
  printf("----table (priority) active entries----\n");
  for (i=0;i<n;i++)
    printf("%d %d\n",i,priority[i]);
  printf("----heap (pq)-----\n");
  for (i=1;i<=N;i++)
    printf("%d %d\n",i,pq[i]);
  printf("----handles (qp)-----\n");
  for (i=0;i<n;i++)
    printf("%d %d\n",i,qp[i]);

  printf("Enter operation (<0 to quit, # of table item, >%d for heapExtractMax)\n",n-1);
  scanf("%d",&op);
  if (op<0)
    break;
  if (op>=n)
    if (maxHeapEmpty())
      printf("Can't do heapExtractMax() when pq is empty\n");
    else
    {
      i=heapExtractMax();
      printf("heapExtractMax() indicates priority[%d]=%d\n",i, priority[i]);
        priority[i]=(-1);
    }
  else
  {
    if (priority[op]<0)
    {
      if (maxHeapFull())
        printf("pq already full\n");
      else
      {
        val=(-1);
        while (val<0)
        {
          printf("Enter non-negative priority to maxHeapInsert() at table slot %d\n",
            op);
          scanf("%d", &val);
        }
        priority[op]=val;
        maxHeapInsert(op);
      }
    }
    else
    {
      val=(-1);
      while (val<0)
      {
        printf("Enter non-negative priority for maxHeapChange() of table slot %d\n",
          op);
        scanf("%d",&val);
      }
      priority[op]=val;
      maxHeapChange(op);
    }
  }
}

free(priority);
free(pq);
free(qp);
}