堆排序的C实现

heap_sort.c

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

void down(int * p, int k, int i)
{

        int value=p[i];
        int t;
        for(t=i*2;t<=k;t=t*2)
        {
                if(t+1 <= k && p[t+1]>p[t])
                        t=t+1;
                if(value<p[t])
                {
                        p[i]=p[t];
                        i=t;
                }
                else
                        break;
        }
        p[i]=value;
}

void build_priority_queue(int * p, int k)
{
        int i;
        for(i=k/2;i>0;i--)
                down(p,k,i);
}

void priority_queue_insert(int * p, int k, int value)
{
        int max=p[1];
        if(value < max)
        {
                p[1]=value;
                down(p,k,1);
        }
}

void priority_queue_adjust(int * p, int k)
{
        int i;
        for(i=k;i>1;i--)
        {
                int temp=p[i];
                p[i]=p[1];
                p[1]=temp;

                down(p,i-1,1);
        }
}

int main(void)
{
        int n,k;

        while(scanf("%d %d",&n,&k) != EOF)
        {
                int i;
                int value;
                int * p=(int *)malloc((n+1)*sizeof(int));
                for(i=1;i<=n;i++)
                {
                        scanf("%d",&value);
                        p[i]=value;
                }

                build_priority_queue(p,k);

                for(i=n;i>k;i--)
                {
                        priority_queue_insert(p,k,p[i]);
                }

                priority_queue_adjust(p,k);

                for(i=1;i<=k;i++)
                {
                        printf("%d",p[i]);
                        if(i != k)
                                printf(" ");
                        else
                                printf("\n");
                }

                free(p);
        }
        return 0;
}