c14-1.c

/* code: c14-1.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#define MAX_PQ_SIZE 128
#define NODE_PARENT(x) ((x - 1) / 2)
#define NODE_LEFT(x) (2 * x + 1)
#define NODE_RIGHT(x) (2 * x + 2)

struct node {
  int priority;
  char data[32];
};
typedef struct node NODE;

struct p_queue {
  int size;
  NODE *elm;
};
typedef struct p_queue P_QUEUE;

/* ------------------------------------------- */
void pq_node_swap (NODE * n1, NODE * n2) {
  NODE node_temp;
  node_temp = *n1;
  *n1 = *n2;
  *n2 = node_temp;
}

/* ------------------------------------------- */
P_QUEUE pq_init (int size) {
  P_QUEUE pq;
  pq.size = 0;
  pq.elm = malloc (size * sizeof (NODE));
  return pq;
}

/* ------------------------------------------- */
void pq_delete_all (P_QUEUE * pq) {
  free (pq->elm);
}

/* ------------------------------------------- */
void pq_display (P_QUEUE * pq) {
  int i;
  for (i = 0; i < pq->size; i++) {
    printf ("heap    (%d) (%s)\n", pq->elm[i].priority, pq->elm[i].data);
  }
}

/* ------------------------------------------- */
void pq_heapify (P_QUEUE * pq, int i) {
  int max;
  max = ((NODE_LEFT (i) < pq->size)
	 && (pq->elm[NODE_LEFT (i)].priority >
	     pq->elm[i].priority)) ? NODE_LEFT (i) : i;

  if ((NODE_RIGHT (i) < pq->size)
      && (pq->elm[NODE_RIGHT (i)].priority > pq->elm[max].priority)) {
    max = NODE_RIGHT (i);
  }
  if (max != i) {
    pq_node_swap (&(pq->elm[i]), &(pq->elm[max]));
    pq_heapify (pq, max);
  }
}

/* ------------------------------------------- */
void pq_enqueue (P_QUEUE * pq, int priority, char *data) {
  NODE node;
  int i;

  node.priority = priority;
  sprintf (node.data, "%s", data);
  printf ("enqueue (%2d)(%s)\n", node.priority, node.data);
  i = (pq->size)++;
  while (i && node.priority > pq->elm[NODE_PARENT (i)].priority) {
    pq->elm[i] = pq->elm[NODE_PARENT (i)];
    i = NODE_PARENT (i);
  }
  pq->elm[i] = node;
}

/* ------------------------------------------- */
void pq_dequeue (P_QUEUE * pq) {
  if (pq->size) {
    printf ("dequeue (%2d)(%s)\n", pq->elm[0].priority, pq->elm[0].data);
    pq->elm[0] = pq->elm[--(pq->size)];
    pq->elm = realloc (pq->elm, pq->size * sizeof (NODE));
    pq_heapify (pq, 0);
  }
  else {
    printf ("priority queue is empty\n");
  }
}

/* ------------------------------------------- */
int main () {
  P_QUEUE pq;
  int i;

  pq = pq_init (MAX_PQ_SIZE);
  pq_enqueue (&pq, 40, "grape");
  pq_enqueue (&pq, 30, "pear");
  pq_enqueue (&pq, 10, "banana");
  pq_enqueue (&pq, 20, "watermelon");
  pq_enqueue (&pq, 50, "apple");
  pq_enqueue (&pq, 60, "lemon");
  pq_display (&pq);
  for (i = 0; i < 7; i++) {
    pq_dequeue (&pq);
  }
  pq_delete_all (&pq);

  return 0;
}

c14-2.c

/* code: c14-2.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%02d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int heap_max (int *v, int n, int i, int j, int k) {
  int max;

  max = i;
  if ((j < n) && (v[j] > v[max])) {
    max = j;
  }
  if ((k < n) && (v[k] > v[max])) {
    max = k;
  }
  return max;
}

/* ------------------------------------------- */
void downheap (int *v, int n, int i) {
  int left, right, j, temp;
  while (1) {
    left = 2 * i + 1;
    right = 2 * i + 2;
    j = heap_max (v, n, i, left, right);
    if (j == i) {
      break;
    }
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
    i = j;
  }
}

/* ------------------------------------------- */
void heapsort (int *v, int n) {
  int i, temp;
  for (i = (n - 2) / 2; i >= 0; i--) {
    downheap (v, n, i);
  }
  for (i = 0; i < n; i++) {
    temp = v[n - i - 1];
    v[n - i - 1] = v[0];
    v[0] = temp;
    downheap (v, n - i - 1, 0);
  }
}

/* ------------------------------------------- */
int main () {
  int array[10]
  = { 80, 40, 30, 20, 10, 00, 70, 90, 50, 60 };

  print_array (array, 10);
  heapsort (array, 10);
  print_array (array, 10);

  return 0;
}

q14-1.c

/* code: q14-1.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int heap_max (int *v, int n, int i, int j, int k) {
  int max;

  max = i;
  if ((j < n) && (v[j] > v[max])) {
    max = j;
  }
  if ((k < n) && (v[k] > v[max])) {
    max = k;
  }
  return max;
}

/* ------------------------------------------- */
void downheap (int *v, int n, int i) {
  int left, right, j, temp;
  while (1) {
    left = 2 * i + 1;
    right = 2 * i + 2;
    j = heap_max (v, n, i, left, right);
    if (j == i) {
      break;
    }
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
    i = j;
  }
}

/* ------------------------------------------- */
void heapsort (int *v, int n) {
  int i, temp;
  for (i = (n - 2) / 2; i >= 0; i--) {
    downheap (v, n, i);
  }
  for (i = 0; i < n; i++) {
    temp = v[n - i - 1];
    v[n - i - 1] = v[0];
    v[0] = temp;
    downheap (v, n - i - 1, 0);
  }
}


/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}

/* ------------------------------------------- */
int main () {
  int *array;

  array = malloc (sizeof (int) * MAX);

  rand_data (array, MAX);
  print_array (array, 20);
  heapsort (array, MAX);
  print_array (array, 20);

  free (array);
  return 0;
}

q14-2.c

/* code: q14-2.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 100000000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int heap_max (int *v, int n, int i, int j, int k) {
  int max;

  max = i;
  if ((j < n) && (v[j] > v[max])) {
    max = j;
  }
  if ((k < n) && (v[k] > v[max])) {
    max = k;
  }
  return max;
}

/* ------------------------------------------- */
void downheap (int *v, int n, int i) {
  int left, right, j, temp;
  while (1) {
    left = 2 * i + 1;
    right = 2 * i + 2;
    j = heap_max (v, n, i, left, right);
    if (j == i) {
      break;
    }
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
    i = j;
  }
}

/* ------------------------------------------- */
void heapsort (int *v, int n) {
  int i, temp;
  for (i = (n - 2) / 2; i >= 0; i--) {
    downheap (v, n, i);
  }
  for (i = 0; i < n; i++) {
    temp = v[n - i - 1];
    v[n - i - 1] = v[0];
    v[0] = temp;
    downheap (v, n - i - 1, 0);
  }
}


/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}

/* ------------------------------------------- */
int main () {
  int *array;

  array = malloc (sizeof (int) * MAX);

  rand_data (array, MAX);
  print_array (array, 20);
  heapsort (array, MAX);
  print_array (array, 20);

  free (array);
  return 0;
}

q14-3.c

/* code: q14-3.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 100000000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int heap_max (int *v, int n, int i, int j, int k) {
  int max;

  max = i;
  if ((j < n) && (v[j] > v[max])) {
    max = j;
  }
  if ((k < n) && (v[k] > v[max])) {
    max = k;
  }
  return max;
}

/* ------------------------------------------- */
void downheap (int *v, int n, int i) {
  int left, right, j, temp;
  while (1) {
    left = 2 * i + 1;
    right = 2 * i + 2;
    j = heap_max (v, n, i, left, right);
    if (j == i) {
      break;
    }
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
    i = j;
  }
}

/* ------------------------------------------- */
void heapsort (int *v, int n) {
  int i, temp;
  for (i = (n - 2) / 2; i >= 0; i--) {
    downheap (v, n, i);
  }
  for (i = 0; i < n; i++) {
    temp = v[n - i - 1];
    v[n - i - 1] = v[0];
    v[0] = temp;
    downheap (v, n - i - 1, 0);
  }
}


/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}


/* ------------------------------------------- */
int main () {
  int *array;
  clock_t start, end;
  double elapsed_in_seconds;

  array = malloc (sizeof (int) * MAX);
  rand_data (array, MAX);
  print_array (array, 20);

  start = clock ();
  heapsort (array, MAX);
  end = clock ();

  print_array (array, 20);

  elapsed_in_seconds = (end - start) / (double) CLOCKS_PER_SEC;
  printf ("%lf seconds\n", elapsed_in_seconds);
  free (array);
  return 0;
}

q14-4.c

/* code: q14-4.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

#define MAX 100000000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int heap_max (int *v, int n, int i, int j, int k) {
  int max;

  max = i;
  if ((j < n) && (v[j] > v[max])) {
    max = j;
  }
  if ((k < n) && (v[k] > v[max])) {
    max = k;
  }
  return max;
}

/* ------------------------------------------- */
void downheap (int *v, int n, int i) {
  int left, right, j, temp;
  while (1) {
    left = 2 * i + 1;
    right = 2 * i + 2;
    j = heap_max (v, n, i, left, right);
    if (j == i) {
      break;
    }
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
    i = j;
  }
}

/* ------------------------------------------- */
void heapsort (int *v, int n) {
  int i, temp;
  for (i = (n - 2) / 2; i >= 0; i--) {
    downheap (v, n, i);
  }
  for (i = 0; i < n; i++) {
    temp = v[n - i - 1];
    v[n - i - 1] = v[0];
    v[0] = temp;
    downheap (v, n - i - 1, 0);
  }
}


/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}


/* ------------------------------------------- */
int main () {
  int *array;
  struct timeval start, end;
  double elapsed_in_seconds;

  array = malloc (sizeof (int) * MAX);
  rand_data (array, MAX);
  print_array (array, 20);

  gettimeofday (&start, NULL);
  heapsort (array, MAX);
  gettimeofday (&end, NULL);

  print_array (array, 20);

  elapsed_in_seconds = difftime (end.tv_sec, start.tv_sec) +
    difftime (end.tv_usec, start.tv_usec) / 1000000.0;
  printf ("%lf seconds\n", elapsed_in_seconds);
  free (array);
  return 0;
}