堆排序heapsort的C实现

    堆排序，过去写过一次，最近写了很多排序算法，比上次实现，代码写的明显熟练了很多，最近的学习，有很多的进步。

    堆排序的算法优先级是NlogN。但是堆排序的性能是不如快速排序。高德纳老爷子的计算机程序设计艺术卷三 P148，提到：

    when N =1000， MIX的平均次数大概为：

    160000u    for  heapsort

    130000u    for  shellsort

    80000u     for  quicksort

    （最小）堆排序还存在另外一个问题，就是每次将最后一个元素和第一个元素交换，最后一个元素一般比较大，几乎总是比第一个元素的两个孩子大，所以比较从概率上将没有多大的含义。把最后的元素放到第一个元素位置上，heap_fixdown几乎总是一路比较，一路下滑。

     我们将堆排序考虑成一个部门的情况。老大退休了，将新入职的员工（即最后一个元素）推上部门老大的位置，然后原老大的两个副手选择出最优秀的一个（最小堆就是谁小谁优秀）和新入职的员工比，如果比新入职的员工优秀，则交换职位。新入职的员工几乎总是肯定败给原老大的两个副手中优秀的那个，新入职的员工从老大，第一层领导，降职为了第二层领导。而优秀的副手升为新的老大。但是新入职的员工变成2层领导，他直接领导的三层领导不乐意了，凭啥 你一个新兵蛋子来当我的领导。于是新入职的员工的两个手下PK出最优秀的，由优秀者代表三层，挑战新兵蛋子的权威，和新兵蛋子一比较，得，新兵蛋子又败了，再次和三层优秀者交换职位。新兵蛋子降为了三层领导。新兵蛋子直接领导的四层，又不乐意了，凭啥你一个新兵蛋子当三层领导，。。。。。悲催的新兵蛋子一路下滑，直到他没有下属了，或者所有的下属不如他优秀。这就是堆排序中删除堆顶元素发生的事情。

    高德纳老爷子的卷三P156的习题18中也提到了这一点。推荐大家阅读刘未鹏的博文

    第一次写的堆排序浪费了空间，需要额外的空间了。所以我改进了第二个版本的heapsort2。堆排序中由于前面是最小堆，每次选出最小的元素放在数组尾，导致，排完之后需要首位对调才能是从小到大排序。为了堆排序的快捷，从小到大排序，请用最大堆，从大到小排序，请用最小堆。

#ifndef _HEAP_H
#define _HEAP_H

#define  father(pos)   ((pos-1)>>1)
#define  firstson(pos) ((pos<<1)+1)
#define secondson(pos)  ((pos+1)<<1)

typedef struct _Heap{
     int *array;
     int number;
     int maxlen;
}Heap;



extern int heap_init(Heap *heap,int maxlen );
extern  int heap_destroy(Heap* heap);
extern void heap_fixup(int array[],int pos);
extern void heap_fixdown(int array[],int pos,int rlimit);
extern int heap_insert(Heap* heap,int value);
extern int heap_delmax(Heap *heap);
extern int heapsort(int array[],int left,int right);

#endif

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include"heap.h"

int test_heapsort()
{
    int i;
    int number = 20;

    int *array = malloc(number*sizeof(int));
    if(array == NULL)
    {
            printf("malloc failed\n");
            return -1;
    }


    printf("----------------------------------------before heap sort------------\n");
    //srand(time(NULL));
    for(i = 0;i<number;i++)
    {
        array[i] = rand()%1000;
        printf("\tarray[%-6d] = %-6d\n",i,array[i]);
    }

    printf("----------------------------------------after heap sort-------------\n");

    heapsort(array,0,number-1);
    for(i = 0;i<number;i++)
    {
        printf("\tarray[%-6d] = %-6d\n",i,array[i]);
    }
    free(array);
    return 0;

}
int main()
{
    test_heapsort();
}

#include
#include
#include"heap.h"

int heap_init(Heap *heap,int maxlen)
{
heap->array = (int *)malloc(maxlen*sizeof(int));
if(heap->array == NULL)
{
            printf("malloc failed for heap_init\n");
   return -1;
}

heap->maxlen = maxlen;
heap->number = 0;
return 0;
}

 int heap_destroy(Heap* heap)

 {

     if(heap->array)

        free(heap->array);

     heap->array = NULL;

     heap->number = 0;

     heap->max->len = 0;

     return 0;

 }

void inline swap(int *x ,int *y)
{
int temp =*x;
*x = *y;
*y = temp;
}


void heap_fixup(int array[],int pos)
{
while(pos>0 && array[pos]
{
               swap(&array[pos],&array[father(pos)]);
      pos = father(pos);
}
}

void heap_fixdown(int array[],int pos,int rlmit)
{
     int j;

       while(firstson(pos) <= rlimit)
       {
       	    j = firstson(pos);
    if(j < rlimit && array[j] >array[j+1])
j++;
    if(array[pos] < array[j])
break;
    swap(&array[pos],&array[j]);
    pos = j;
       }

}


int heap_insert(Heap* heap,int value)
{
if(heap->number +1 >(heap->maxlen))
{
            int *new_array = realloc(heap->array,(heap->maxlen)*2);
   if(new_array == NULL)
   {
 printf("realloc for heap_insert failed\n");
return -1;
   }
            heap->array = new_array;
   heap->maxlen = heap->maxlen <<1;
}

heap->array[heap->number] = value;
heap_fixup(heap->array,heap->number);
heap->number++;
return 0;

}


int heap_delmin(Heap *heap)
{
swap(&(heap->array[0]),&(heap->array[heap->number-1]));
heap->number--;
heap_fixdown(heap->array,0,heap->number-1);
return heap->array[heap->number];/*return the smallest element */
}


int heapsort(int array[],int left,int right)
{
int len;
Heap heap;
int ret;
int pos;

if(array == NULL)
{
              return -1;
}
if(left > right)
{
              return -2;
}
if(left == right)
{
              return  0;
}

len = right - left + 1;
        ret = heap_init(&heap,len);
if(ret <0)
return ret;
for(pos = left ;pos<=right;pos++)
    heap_insert(&heap,array[pos]);

for(pos = left ; pos <= right; pos++)
            array[pos] = heap_delmin(&heap);
        heap_destroy(&heap)
return 0;
}

int heapsort2(int array[],int left ,int right)

{

if(array == NULL)

{

            return -1;

}

if(left > right)

{

            return -2;

}

if( left == right )

{

           return 0;

}

int len = right - left + 1;

        int i;

int * base = &(array[left]);

for(i = father(len-1); i >=0; i --)

{

           heap_fixdown(base,i,len-1);

}

while(len >0)

{

              swap(&base[0], &base[len-1]);

     len--;

     heap_fixdown(base,0,len-1);

}

        /*由于是最小堆，同时从小到大排序，所以需要将数组翻转。如果是最大堆就不用翻转了*/

int mid = (right+left)/2;

for(i = left ;i <= mid;i++)

{

            swap(&array[i],&array[left+right - i]);

}

 

        return 0;

}