数据结构-优先队列的实现

/*
   优先队列包括最大优先队列和最小优先队列，优先队列的应用比较广泛，
   比如作业系统中的调度程序，当一个作业完成后，需要在所有等待调度的作业中
   选择一个优先级最高的作业来执行，并且也可以添加一个新的作业到作业的优先队列中。

   优先队列用于从排队等待处理的任务中每次选择一个“优先级最高的”进程处理。
   这种找最优（最大或最小）通常需要O(n)时间复杂度，
   而“堆”比如“大顶堆”的第一个元素就是最大（最优的）的，删除最大值后
   调整选出剩余最大的只要O(logn)。
   插入一个新的任务也是一样时间复杂度O(logn)，如果采用插入排序，最好也要O(n)

   想象一下，假如n=1024，则logn=10。

   因此，基于堆的优先队列效率就可以很高！

   其抽象数据类型如下：
   ADT Priority_Queue{
       //从队列里出对最优的元素
    remove();
      //加入新的元素进入优先队列
    insert(EType e);
    //得到排在最前面的最优元素，但不删除它
    front(EType *e); 
  }

  //http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html  
*/

#include <stdio.h>

#include <stdlib.h>

#define ERROR 1

#define OK 0

typedef int T;

typedef struct{
  T *data;
  int capacity,n;
}priority_queue;

int init_priority_queue(priority_queue *Q,int cap){
  Q->data  =(T*) malloc((cap+1)*sizeof(T));
  if(!Q->data) return ERROR;
  Q->capacity = cap;
  Q->n = 0 ;
  return OK;
}

int remove_priority_queue(priority_queue *Q){
    if(Q->n==0) return ERROR;
    T t = Q->data[Q->n]; /*Q->data[1] = Q->data[Q->n];*/
    Q->n--;
    int  n = Q->n;
    int s = 1;  
    T *a = Q->data;
  for(int j = 2*s; j <= n; j *= 2) {
    if(j <n  && a[j]< a[j+1] )
      j++;    //j指向s较大的“儿子”
    if(!(t<a[j]) )
       break;  //若j的值比t小，说明找到了s的位置
    a[s] = a[j]; //否则元素j上移
    s = j;
  }
  a[s] = t;   //写入s
  return OK;
}

int insert_priority_queue(priority_queue* Q,T e){
    int n,s; T *a;
    if(Q->n==Q->capacity){
      T *p = (T*)malloc((2*Q->capacity+1)*sizeof(T));
      if(!p) return ERROR;
      free(Q->data);
      Q->data = p;
    }
   
  n = ++Q->n ; s = n;
  a = Q->data;
  for(int j = s/2; j>=1&&a[j]<e; s= j,j/= 2) {
       a[s] = a[j];
  }
  a[s] = e;
  return OK;
}

int front_priority_queue(priority_queue Q,T *e){
  if(Q.n==0) return ERROR;
  *e = Q.data[1];
  return OK;
}
int isEmpty(priority_queue Q){
  if(Q.n==0) return 1;
  return 0;
}

int main(){
  priority_queue Q;
  T e;
  init_priority_queue(&Q,10);
  insert_priority_queue(&Q,5);
  insert_priority_queue(&Q,79);
  insert_priority_queue(&Q,15);
  insert_priority_queue(&Q,3);
  insert_priority_queue(&Q,23);

  while(!isEmpty(Q)){
    front_priority_queue(Q,&e);
    printf("%d\n",e);
    remove_priority_queue(&Q);
  }
  return 0;
}