弄了个优先队列代码~结果发现它竟然无意中实现了堆排序的功能~

堆排序折腾了我些许时间理解~写了优先队列后感觉对堆排序理解容易多了……
问题是堆排序记得要用到递归而优先队列不用……那么优先队列和堆排序还有密切的关系么~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<time.h>

#define MAX_LENGTH 128
#define OK 1
#define ERROR 0


typedef int ElemType;
typedef struct Priority_Queue
{
    int length;
    size_t size;
    ElemType* ElemType;
}Priority_Queue,*P_Priority_Queue;

void Creat_Node(void** p,const size_t size);
void Free_Node(void** p);

void Initilaze_Priority_Queue(P_Priority_Queue queue);  //初始化一个优先队列
void Free_Priority_Queue(P_Priority_Queue queue);       //释放一个优先队列

void Insert_Priority_Queue(P_Priority_Queue queue,ElemType* e);  //插入一个元素
void Get_Priority_Queue(P_Priority_Queue queue,ElemType* e);     //获取顶部的一个元素
void Del_Priority_Queue(P_Priority_Queue queue,ElemType* e);     //获取顶部并删除一个元素
int IsFull_Priority_Queue(P_Priority_Queue queue);              //判断是否满表
int IsEmpty_Priority_Queue(P_Priority_Queue queue);             //判断是否空表

int main()
{
    Priority_Queue queue={0};
    ElemType e=0;
    int i=0;

    srand((unsigned)time(NULL));
    Initilaze_Priority_Queue(&queue);

    puts("测试数据:\n");
    for (i=0;i<10;++i)
    {
        e=rand()%100;    
        printf("%-4d",e);

        Insert_Priority_Queue(&queue,&e);
    }

    puts("\n\n堆内数据排列:\n\n");
    for (i=1;i<=queue.length;++i)
        printf("%-4d",queue.ElemType[i]);

    puts("\n\n获取并删除堆顶数据:\n");
    while (IsEmpty_Priority_Queue(&queue)==OK)
    {
        Del_Priority_Queue(&queue,&e);
        printf("%-4d",e);
    }

    puts("");

    Free_Priority_Queue(&queue);
    
    return 0;
}

void Creat_Node(void** p,const size_t size)
{
    if (*p)
        return ;

    *p=malloc(size);
    assert(*p);
    memset(*p,0,sizeof(size));
}

void Free_Node(void** p)
{
    if (*p==NULL)
        return ;

    free(*p);
    *p=NULL;
}

void Initilaze_Priority_Queue(P_Priority_Queue queue)
{
    Creat_Node((void** )&queue->ElemType,MAX_LENGTH*sizeof(ElemType*));
    queue->size=sizeof(*queue->ElemType);
}

void Free_Priority_Queue(P_Priority_Queue queue)
{
    Free_Node((void** )&queue->ElemType);
}

void Insert_Priority_Queue(P_Priority_Queue queue,ElemType* e)
{
    int i=0;

    if (IsFull_Priority_Queue(queue)==ERROR)
        return ;

    for (i=++queue->length;*e<queue->ElemType[i>>1]&&i>>1>0;i>>=1)
        queue->ElemType[i]=queue->ElemType[i>>1];

    queue->ElemType[i]=*e;
}

void Get_Priority_Queue(P_Priority_Queue queue,ElemType* e)     //获取顶部的一个元素
{
    *e=queue->ElemType[1];
}
void Del_Priority_Queue(P_Priority_Queue queue,ElemType* e)     //获取顶部并删除一个元素
{
    int i=1;
    int k=2;

    int temp=queue->ElemType[queue->length];

    if (IsEmpty_Priority_Queue(queue)==ERROR)
    {
        *e=NULL;
        return ;
    }

    for (*e=queue->ElemType[1],--queue->length;k<=queue->length;i=k,k<<=1)
    {
        if (k+1<=queue->length&&queue->ElemType[k+1]<queue->ElemType[k])
            ++k;

        if (temp<queue->ElemType[k])
            break;

        queue->ElemType[i]=queue->ElemType[k];
    }

    queue->ElemType[i]=temp;
}

int IsFull_Priority_Queue(P_Priority_Queue queue)              //判断是否满表
{
    if (queue->length>MAX_LENGTH-2)
        return ERROR;

    return OK;
}
int IsEmpty_Priority_Queue(P_Priority_Queue queue)            //判断是否空表
{
    if (queue->length==0)
        return ERROR;

    return OK;
}

[此贴子已经被作者于2017-9-20 22:43编辑过]

原意是用优先队列打算用来优化最小生成树问题的时间复杂度~做了之后发现构造堆的方法和我之前写的堆排序的不咋一样~
问题是堆排序那个构造函数n/2次就可以生成堆了~而我那个要n次才行~那是不是意味着我那个效率不够堆排序那个效率高呢~

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

#define MAX 255

int R[MAX]={0};

void Heapify(int s,int m);
void BuildHeap(int n);
void Heap_Sort(int n);

int main()
{
    int i=0;
    int n=0;

    puts("Please input total element number of the sequence:");
    scanf("%d",&n);

    if (n<=0||n>MAX)
    {
        printf("n must more than 0 and less than %d.\n",MAX);
        exit(0);
    }

    puts("Please input the elements one by one:");
    for (i=1;i<=n;++i)
        scanf("%d",&R[i]);

    puts("The sequence you input is:");
    for (i=1;i<=n;++i)
        printf("%4d",R[i]);

    Heap_Sort(n);

    puts("\nThe sequence after Big head_sort is:");
    for (i=1;i<=n;++i)
        printf("%4d",R[i]);

    puts("");

    return 0;
}

void Heapify(int s,int m)
{
    /*对R[1..n]进行堆调整,用temp做暂存单元*/
    int j=2*s;             
    int temp=R[s];

    while (j<=m)
    {
        if (R[j]>R[j+1]&&j<m)
            j++;

        if (temp<R[j])
            break;

        R[s]=R[j];
        s=j;
        j*=2;
    }

    R[s]=temp;
}

void BuildHeap(int n)
{
    /*由一个无序的序列建成一个堆*/
    int i=0;

    for (i=n/2;i>0;--i)
        Heapify(i,n);
}

void Heap_Sort(int n)
{
    /*对R[1..n]进行堆排序,不妨用R[0]做暂存单元*/
    int i=0;

    BuildHeap(n);

    for (i=n;i>1;--i)
    {
        R[0]=R[1];     /*将堆顶和堆中最后一个元素记录交换*/
        R[1]=R[i];
        R[i]=R[0];

        Heapify(1,i-1);  /*将R[1..i-1]重新调整为堆,仅有R[1]可能违反堆性质*/
    }


}

明白了~原来建堆有两种方法~一种是自顶向底构建~另一种是自底向顶构建~其实都是能够实现的~

编程论坛 - 求一个优先队列的C代码~

https://bbs.bccn.net/thread-479134-1-1.html

哇~原来和renkejun1942提供的代码差不多~我自己也服了~