c语言堆排序代码

#include<液戚stdio.h>

void shift(int a[] , int i , int m)

{

int k , t

t = a[i]k = 2 * i + 1

while (k <m)

{

if ((k <m - 1) &&(a[k] <a[k+1])) k ++

if (t <a[k]) {a[i] = a[k]i = kk = 2 * i + 1}

else break

}

a[i] = t

}

void heap(int a[] , int n) //辩正a 为排序数组，n为数组大小（携埋悔编号0-n-1）

{

int i , k

for (i = n/2-1i >= 0i --) shift(a , i , n)

for (i = n-1i >= 1i --)

{

k = a[0]a[0] = a[i]a[i] = k

shift(a , 0 , i)

}

}

void main()

{

int a[10],i

for(i=0i<10i++)

scanf("%d",&a[i])

heap(a,10)

for(i=0i<10i++)

printf("%d",a[i])

}

        堆排序是一个比较优秀的算法,堆这种数据结构在现实生活中有很多的应用,比如堆可以作为一个优先队列来使用,作为一个高效的优先队列,它与堆的结构一样,都有最大优先队列,最小优先队列.优先队列priority queue 是一种用来维护一组元素构成的集合S的数据结构，每一个元素都有一个相关的值，称为关键字（key）。

        最大优先队列包含以下 *** 作：

         将元素x插入到S的集合中，等价于 ；

         返回S中最大元素；

         返回并且删除S中最大元含李素；

         将元素x的关键字增加到key，要求 。

        同样的，最小优先队列 *** 作也包括： , , , 。只不过是对最小值进行 *** 作。

        在这里主要讨论最大优先队列，其应用很多，在共享计算机作业系统就是，类似于早期的unix主机，管理员root可以设置n个不同的用户，以及各个用户不同的 *** 作权限，从主机那里接出多个终端，每个 *** 作人员（程序员）在自己的工作终端 ，感觉像是自己拥有自己独立的作业主机一样，其实不是，通过一些任务调度来实现，其中就有任务等待执行相关队列，并且有各个任务有着自己优先级，以便确定调度执行具体任务，如果你学过 *** 作系统相关知识，那么应该对系统调度有所了解。

        当一个作业被完成或者被中断后，调度器会调用 来调用所有在队列中等待任务中优先级最高的任务执行，在新任务加入等待任务时会配稿调用 加入任务等待队列，当某个任务等待时间过长时可通过 提高其优先级培老孝，从而减少等待时间。

        下面是具体实现C程序源码：

#include <stdio.h>

#define NAGE_INFINIT -99999

#define parent(i) i/2

#define left(i) 2*i+1

#define right(i) 2*i+2

//get array of A first element

int heap_maximum(int A[]){ return A[0]}

/***********************************************

*

* function max_heapify()

*

* args

*  A[] inttype save elements of heap

*  i index of A

*  heap_size real length of A

*

* ********************************************/

void max_heapify(int A[],int i,int heap_size){

    int l,r,largest,temp

    l=left(i)

    r=right(i)

    if((l<=heap_size)&&(A[l]>A[i]))

        largest=l

    else

        largest=i

    if((r<=heap_size)&&(A[r]>A[largest]))

        largest=r

    if(largest!=i){

        temp=A[i]

        A[i]=A[largest]

        A[largest]=temp

        max_heapify(A,largest,heap_size)

    }

}

/*********************************************

*

* function heap_extract_max()

*

* args

*  A[] inttype save elements of heap

*  heap_size inttype the real length of A

*

* return max the parent node value

*

* ******************************************/

int heap_extract_max(int A[],int heap_size){

    int max

    if(heap_size<0)

        return -1  //heap underflow

    max=A[0]  //parent node the max value of element

    A[0]=A[heap_size]

    heap_size--

    /**************************************

    * dajust binary heap(or tree) to make

    * sure heap fo A true every times

    *

    * ************************************/

    max_heapify(A,0,heap_size)

    return max

}

/***********************************************

*

* function heap_increase_key()

*

* args

*  A[] inttype save elemnts of heap

*  i index of A

*  key inserted element

*

* *********************************************/

void heap_increase_key(int A[],int i,int key){

    int temp

    if(key<A[i]){

        printf("new key is smaller than current key\n")

        return    //over programming

    }

    A[i]=key

    //p=parent(i)

    while ((i>0)&&(A[parent(i)]<A[i])) {

        temp=A[i]

        A[i]=A[parent(i)]

        A[parent(i)]=temp

        i=parent(i)//update index of A

        //p=parent(i)

    }

}

/***************************************************

*

* function max_heap_insert()

*

* args

*  A[] inttype save elements of A

*  key inserted element to A

*  heap_size real length of A

*

* **************************************************/

void max_heap_insert(int A[],int key,int heap_size){

    heap_size+=1

    A[heap_size]=NAGE_INFINIT

    heap_increase_key(A,heap_size,key)

}

int main()

{

    int heap_max,max,i,key

    int A[11],Temp[11]

    int heap_size=0

    char c

    while (1) {

        scanf("%d",&A[heap_size])

        c=getchar()

        if(c=='\n')

            break

        heap_size++

    }

    //copy A to Temp

    for(i=0i<=heap_sizei++)

        Temp[i]=A[i]

    //get heap maximum element

    heap_max=heap_maximum(A)

    printf("heap of A maximum element: %d\n",heap_max)

    //copy Temp to A

    for(i=0i<=heap_sizei++)

        A[i]=Temp[i]

    /*--extract maximum element--*/

    max=heap_extract_max(A,heap_size)

    printf("extract element: %d \n",max)

    printf("new heap of A after extract maximum node\n")

    for(i=0i<heap_sizei++)

        printf("%d ",A[i])

    printf("\n")  //next line

    //copy Temp to A

    for(i=0i<=heap_sizei++)

        A[i]=Temp[i]

    /*--increase from A[i] to key--*/

    printf("input i key ")

    scanf("%d %d",&i,&key)

    heap_increase_key(A,i,key)

    for(i=0i<=heap_sizei++)

        printf("%d ",A[i])

    printf("\n")

    //copy Temp to A

    for(i=0i<=heap_sizei++)

        A[i]=Temp[i]

    /*--insert queueu--*/

    key=0  //init key

    printf("input key: ")

    scanf("%d",&key)

    max_heap_insert(A,key,heap_size)

    for(i=0i<=heap_size+1i++)

        printf("%d ",A[i])

    printf("\n")

    return 0

}

/****************************************

*

* input 16 14 10 8 7 9 3 2 4 1

*      i: 8

*      key: 15

*

* output in function main()

* **************************************/

其运行结果如下图：

欢迎留言交流，也感谢指正，一起进步。

---