janqii

堆排序的时间复杂度和合并排序时间复杂度一样是O(n*lgn)。

堆排序可以原地排序，这一点上优于合并排序（需要一个辅助数组）；插入排序也是原地排序，可是时间复杂度是O(n^2)

1、保持堆（大顶堆）的性质的算法（A是输入堆，从i开始保持大顶堆的性质）：

max_heapify(A,i)
    l=LEFT(i)
    r=RIGHT(i)
    if(l<=heap_size(A)&&A[l]>A[i]）
            then largest=l
    else largest=i
    if(r<=heap_size(A)&&A[r]>A[largest])
           largest=r
    if(largest!=i)
           then exchange A[i]<->A[largest]
          max_heapify(A,largest)

2、建堆（从最后一个非叶子节点开始使其保持堆的性质）：

共有n个元素，则最后一个非叶子节点位置是n/2。

不妨设最后一个非叶子节点为(n+1)/2，则其左孩子是n+1>n，矛盾，所以是n/2，则算法描述为

build_maxHeap(A)
    for i=heap_size(A)/2 downto 1
           do max_heapify(A,i)

3、堆排序

首先建立大顶堆，然后把根元素（最大元素）与最后一个叶子节点交换位置，heap-size--，然后从根元素开始调整堆，使其保持大顶堆的性质。

算法描述为

   heap_sort(A)
           build_maxHeap(A)
          for i=heap_size(A) downto 2
               do exchange A[1]<->A[i]
                    heap_size(A)=heap_size(A)-1
                    max_heapify(A,1)

-------------------------------------------------示例演示---------------------------------------------------------------------

示例输入：9                 /*堆大小*/

                  5                 /*元素个数*/

                  1 5 2 4 3     /*输入元素值*/

输出：5 4 3 2 1

-------------------------------------------------C代码实现---------------------------------------------------------------------

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

#define LEFT(i)   2*i
#define RIGHT(i) 2*i+1
#define PARENT(i) i/2

struct HeapType{
int *base;   /*base[0]存放heap_size，因此heap_size字段也可以去掉*/
int length;
int heap_size; /*可去掉，用base[0]来代替*/
};

void max_heapify(struct HeapType heap,int i);
void build_maxHeap(struct HeapType heap);
void heap_sort(struct HeapType heap);
void swap(int *val1,int *val2);

int main(void)
{
int i=-1;
int n=-1;
int val=-1;
struct HeapType heap;

heap.length=0;
heap.heap_size=0;

scanf("%d",&n);

heap.length=n;
heap.base=(int*)malloc((heap.length+1)*sizeof(int));

scanf("%d",&heap.heap_size);

if(heap.heap_size>heap.length)
   return -1;

for(i=1;i<=heap.heap_size;i++)
{
   scanf("%d",&val);
   heap.base[i]=val;
   /*heap.heap_size +=1;*/
}

heap.base[0]=heap.heap_size;
i=heap.heap_size;

heap_sort(heap);
for( ;i>0;i--)
   printf("%d ",heap.base[i]);

return 0;
}

void max_heapify(struct HeapType heap,int i)
{
int largest=-1;
int l=LEFT(i);
int r=RIGHT(i);

if(l<=heap.heap_size && heap.base[l]>heap.base[i])
   largest=l;
else
   largest=i;

if(r<=heap.heap_size && heap.base[r]>heap.base[largest])
   largest=r;

if(largest!=i)
{
   swap(&heap.base[largest],&heap.base[i]);
   max_heapify(heap,largest);
}   
}

void build_maxHeap(struct HeapType heap)
{
int i=-1;

for(i=(heap.heap_size)>>1;i>0;i--)
   max_heapify(heap,i);
}

void heap_sort(struct HeapType heap)
{
int i=-1;

build_maxHeap(heap);

for(i=heap.heap_size;i>1;i--)
{
   swap(&heap.base[1],&heap.base[i]);
   heap.heap_size -=1;
   max_heapify(heap,1);
}
}

void swap(int *val1,int *val2)
{
int tmp=*val1;
*val1=*val2;
*val2=tmp;
}