【425】堆排序方法

// pq.h: ADT interface for a priority queue
#include <stdio.h>
#include <stdlib.h>

typedef struct pqRep *PQ;

PQ   createPQ(int size);
void insertPQ(PQ q, int it);
int  delMaxPQ(PQ q);
int  isEmptyPQ(PQ q);

/* pqSort.c: use a priority queue to sort an array of integers
             into descending order
 */
#include "pq.h"

int main() {
   int a[] = {41, 2, 58, 156, 360, 81, 260, 74, 167, 13};
   int length = sizeof(a)/sizeof(a[0]);

   PQ q = createPQ(length);
   printf("Array: ");
   for (int i = 0; i < length; i++) {
       printf("%d ", a[i]);
       insertPQ(q, a[i]);
   }
   printf("\nSorted: ");
   while (!isEmptyPQ(q)) {
       printf("%d ", delMaxPQ(q));
   }
   putchar(‘\n‘);
   return EXIT_SUCCESS;
}

// pqHP.c: priority queue implementation for pq.h using a heap
#include "pq.h"

// ‘static‘ means these functions are for local use only
static void fixDown(int *, int, int);
static void fixUp(int *, int);

// Priority queue implementation using an unordered array
struct pqRep {
   int nItems;  // actual count of Items
   int *items;  // array of Items
   int maxsize; // maximum size of array
};

PQ createPQ(int size) {
   PQ q = malloc(sizeof(struct pqRep));  // make room for the structure
   if (q == NULL) {
      fprintf(stderr, "out of memory\n");
      exit(0);
   }
   q->items = malloc((size+1) * sizeof(int)); // make room for the array
   if (q->items == NULL) {                // size+1 because heap 1..size
      fprintf(stderr, "out of memory\n");
      exit(0);
   }
   q->nItems = 0;                          // we have no items yet
   q->maxsize = size;                      // remember the maxsize
   return q;                               // return the initial PQ
}

void insertPQ(PQ q, int it) {
    if (q == NULL) {
       fprintf(stderr, "priority queue not initialised\n");
       exit(1);
    }
    if (q->nItems == q->maxsize) {
       fprintf(stderr, "priority queue full\n");
       exit(1);
    }
    q->nItems++;                    // adding another item
    q->items[q->nItems] = it;       // put the item at the end
    fixUp(q->items, q->nItems);     // fixUp all the way to the root
    return;
}

int delMaxPQ(PQ q) {
   if (q == NULL) {
      fprintf(stderr, "priority queue not initialised\n");
      exit(1);
   }
   if (q->nItems == 0) {
      fprintf(stderr, "priority queue empty\n");
      exit(1);
   }
   int retval = q->items[1];          // this is the item we want to return
   q->items[1] = q->items[q->nItems]; // overwrite root by last item
   q->nItems--;                       // we are decreasing heap size by 1
   fixDown(q->items, 1, q->nItems);   // fixDown the new root
   return retval;
}

int isEmptyPQ(PQ q) {
   int empty = 0;
   if (q == NULL) {
      fprintf(stderr, "isEmptyPQ: priority queue not initialised\n");
   }
   else {
      empty = q->nItems == 0;
   }
   return empty;
}

// fix up the heap for the ‘new‘ element child
void fixUp(int *heap, int child) {
   while (child>1 && heap[child/2]<heap[child]) {
      int swap = heap[child];         // if parent < child, do a swap
      heap[child] = heap[child/2];
      heap[child/2] = swap;
      child = child/2;                // become the parent
   }
   return;
}

// force value at a[par] into correct position 
void fixDown(int *heap, int par, int len) {
   int finished = 0;
   while (2*par<=len && !finished) {// as long as you are within bounds
      int child = 2*par;          // the first child is here
      if (child<len && heap[child]<heap[child+1]) {
         child++;                 // choose larger of two children
      }
      if (heap[par]<heap[child]) { // if node is smaller than this child ...
         int swap = heap[child];   // if parent < child, do a swap
         heap[child] = heap[child/2];
         heap[child/2] = swap;
         par = child;             // ... and become this child
      }
      else {
         finished = 1;            // else we do not have to go any further
      }
   }
   return;
}

prompt$ dcc pqHP.c pqSort.c
prompt$ ./a.out
Array: 41 2 58 156 360 81 260 74 167 13 
Sorted: 360 260 167 156 81 74 58 41 13 2