我所理解的堆排序算法
      堆排序在最坏的情况下,其时间复杂度也能达到O(nlogn)。相对于快速排序来说,这是它最大的优点,此外,堆排序仅需要一个记录大小供交换用的辅助存储空间。
      堆排序的数据结构是二叉堆,二叉堆的特点有两个,一个是它是一棵完全二叉树,另一个是它的根结点小于孩子结点,所以我们很容易找到它的最小结点----根结点;当然如果你想找到最大结点的话,那就要扫描所有的叶子结点,这是很费时间的,如果你想找的是最大结点的话,你最好把它弄成一个大顶堆,即一棵根结点大于孩子结点的完全二叉树。
      二叉堆通常用数组来实现,它舍弃下标0,从下标1开始置数,则很容易满足,对于数组中任意位置i上的元素,其左儿子的位置在2i上,右儿子的位置在2i+1上,双亲的位置则在i/2上。
      堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间,然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根,把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1,并通过上移使得新得到的序列仍为二叉堆,再提取新二叉堆的第一个元素到新数组。依此类推,直到提取最后一个元素,新得到的数组就是排序后的数组。
算法如下:
template <class T>
void Insert(T a[], int len, T x)//把x插入到原长度为len的二叉堆,注意保证新二叉堆不越界
{
      int i;
      for (i=len; i/2>0 && a[i/2]>x; i/=2)
            a[i] = a[i/2];
      a[i] = x;
}

template <class T>
T DeleteMin(T a[], int len)//删除二叉堆的根,并通过上移使得新得到的序列仍为二叉堆
{
      if (len == 0)
            exit(1);
      T min = a[1];//二叉堆的根
      T last = a[len--];//二叉堆的最后一个元素

      int c;
      int i;
      for (i=1; i*2<=len; i=c)//把二叉堆的某些元素往前移,使得新得到的序列仍为二叉堆
      {
            c = i * 2;//i的左儿子
            if (c != len && a[c+1] < a[c])//若i有右儿子,且右儿子小于左儿子,c指向右儿子
                  c++;

            if (last > a[c])//若i的小儿子小于二叉堆的最后一个元素,把其移到i的位置
                  a[i] = a[c];
            else
                  break;
      }
      a[i] = last; //把二叉堆的最后一个元素放到适当的空位,此时得到的序列仍为二叉堆

      return min;
}

template <class T>
void HeapSort(T a[], int len)
{
      T *ca = new T[len+1]; //复制原数组到二叉堆
      ca[0] = 0;
      for (int i=0; i<len; i++) //把元素依次插入到二叉堆
            Insert(ca, i+1, a[i]);

      for (int i=0; i<len; i++)//依次提取二叉堆的根作为排序后的数组的元素
      {
            a[i] = DeleteMin(ca, len-i);
      }

      a[len-1] = ca[1]; //注意不能忘了最后一个元素

      delete []ca;
}
      在《数据结构习题与解析》(李春葆 编著 清华大学出版社)中看到一个类似的算法,它是把原数组构建成一个大顶堆,然后把大顶堆的第一个元素与最后一个元素交换;再把前n-1个元素重新构造成一个大顶堆,把新大顶堆的第一个元素与最后一个元素交换;依此类推,直到新大顶堆只有一个元素,这样就得到了一个有序的二叉堆。
算法如下:
template <class T>
void HeapSort(T a[], int len)
{
      T *ca = new T[len+1];
      ca[0] = 0;
      for (int i=0; i<len; i++)
            ca[i+1] = a[i];

      for (int i=len/2; i>0; i--) //建立初始堆
            HeapAdjust(ca, len, i);

      for (int i=len; i>1; i--)//进行len-1次循环,完成堆排序
      {
            Swap(ca[1], ca[i]); //新大顶堆的第一个元素与最后一个元素交换
            HeapAdjust(ca, i-1, 1);//筛a[1]元素,得到i-1个元素的堆
      }

      for (int i=0; i<len; i++)
            a[i] = ca[i+1];

      delete []ca;
}

template <class T>
void HeapAdjust(T a[], int len, int left) //将i与其小儿子交换位置
{
      if (len == 0)
            exit(1);

      T x = a[left];
      int i = left;
      int c = 2 * i;
      while (c <= len)
      {
            if (c < len && a[c+1] > a[c])//若i有右儿子,且右儿子大于左儿子,c指向右儿子
                  c++;
            if (last < a[c])//若i的大儿子大于二叉堆的最后一个元素,把其移到i的位置
            {
                  a[i] = a[c];
                  i = c;
                  c = 2 * i;
            }
            else
                  break;
      }
      a[i] = x; //把原二叉堆的第一个元素放到适当的空位
}

template <class T>
void Swap(T & a, T & b)
{
      T t = a;
      a = b;
      b = t;
}

      还有一种方法是每次都要重新调整大顶堆,使得父亲比儿子大,这样调整的函数较简单,
但因为每次都要遍历一半的元素,时间复杂度较大。
算法如下:
template <class T>
void HeapSort(T a[], int len)
{
      T *ca = new T[len+1];
      ca[0] = 0;
      for (int i=0; i<len; i++)
            ca[i+1] = a[i];

      for (int i=len/2; i>0; i--) //把原数组构建成一个大顶堆
            HeapAdjust(ca, len, i);
      Swap(ca[1], ca[len]); //把大顶堆的第一个元素与最后一个元素交换
     
      for (int i=len-1; i>0; i--)
      {
            for (int j=i/2; j>0; j--)//遍历长度为i的堆,得到新的大顶堆
                  HeapAdjust(ca, i, j);
            Swap(ca[1], ca[i]);
      }
     
      for (int i=0; i<len; i++)
            a[i] = ca[i+1];

      delete []ca;
}

template <class T>
void HeapAdjust(T a[], int len, int i) //将i与其小儿子交换位置
{
      int c = 2 * i;

      if (c < len)
      {
            T & max = (a[c] > a[c+1])? a[c] : a[c+1];
            if (a[i] < max)
                  Swap(a[i], max);
      }
      else
      {
            if (a[i] < a[c])
                  Swap(a[i], a[c]);
      }
}

template <class T>
void Swap(T & a, T & b)
{
      T t = a;
      a = b;
      b = t;
}

      模仿构造大顶堆的方法,我们可以调用HeapAdjust()构造一个二叉堆,并提取二叉堆的根到新数组,
然后把原二叉堆的最后一个元素放到根的位置,再调用HeapAdjust()构造一个新二叉堆,依此类推。
算法如下:
template <class T>
void HeapSort(T a[], int len)
{
      T *ca = new T[len+1];
      ca[0] = 0;
      for (int i=0; i<len; i++)
            ca[i+1] = a[i];

      for (int i=len/2; i>0; i--) //把原数组构建成一个大顶堆
            HeapAdjust(ca, len, i);
      a[0] = ca[1];
      ca[1] = ca[len]; //把二叉堆的最后一个元素放到根的位置

      for (int i=len-1; i>0; i--)
      {
            for (int j=i/2; j>0; j--)
                  HeapAdjust(ca, i, j);
            a[len-i] = ca[1];
            ca[1] = ca[i]; //把二叉堆的最后一个元素放到根的位置
      }

      delete []ca;
}

template <class T>
void HeapAdjust(T a[], int len, int i)
{
      int c = 2 * i;

      if (c < len)
      {
            T & min = (a[c] < a[c+1])? a[c] : a[c+1];
            if (a[i] > min)
                  Swap(a[i], min);
      }
      else
      {
            if (a[i] > a[c])
                  Swap(a[i], a[c]);
      }
}

template <class T>
void Swap(T & a, T & b)
{
      T t = a;
      a = b;
      b = t;
}
      后面两种方法采用的是递归,容易理解,但时间复杂度较高,因为比前两种要慢上很多,所以不可能是O(nlogn),估计是O(n^2),但具体我也不会算,请高手指教。

Posted on 2006-06-14 10:18 梦想飞扬 阅读(4242) 评论(2)  编辑 收藏 引用

Feedback

# re: 我所理解的堆排序算法  回复  更多评论   

2006-10-17 01:49 by 李伟
#define HEAP_MAX_LEN 100
#define DataType int
static DataType heap_table[HEAP_MAX_LEN+1];
static int current_size=0;

void minheap_init(void){
int i;
for(i=0;i<1+HEAP_MAX_LEN;++i)
heap_table[i]=0;
current_size = 0 ;
}

void minheap_filterdown(int start ,int end){
int i= start;//i and father while j as child
int j= i*2+1;
DataType temp= heap_table[i];
while(j<=end)
{
if (heap_table[j]>heap_table[j+1])j++;
if (temp<=heap_table[j])break;
else {
heap_table[i]=heap_table[j];i=j;j=2*j+1;
}
}
heap_table[i]=temp;
}
/*
void swap(DataType *a,DataType *b){
DataType t;
t=*a;*a=*b;*b=t;
}
*/
void minheap_filterup(int start){
int j=start;//i as child while j and father
int i=(j-1)/2;
DataType temp=heap_table[j];
while(j>0){
if (heap_table[i]<=temp)break;
else {heap_table[j]=heap_table[i];j=i;i=(i-1)/2;}
heap_table[j]=temp;
}
}

DataType minheap_fetch(void ){
DataType ret;
if (current_size==0){printf("heap is now empty!\n");}
ret=heap_table[0];heap_table[0]=heap_table[current_size-1];
current_size--;
minheap_filterdown(0,current_size-1);
return ret;
}

int minheap_insert(DataType x){
if (current_size>=HEAP_MAX_LEN){printf("heap is now full!\n");return 0 ;}
heap_table[current_size]= x;
minheap_filterup(current_size);
current_size++;
return 1;
}
int fill[]={8,9,10,7,6,5,2,3,4,1,29,45,67,890};
int main(){
int i=0;
int cnt = sizeof (fill)/4;
minheap_init();
while(i!=cnt){
if (minheap_insert(fill[i])==0)break;
++i;
}
i= 0;
while(i!=cnt){// printf("%d get one from minheap==>%d\n",current_size,heap_table[i]);

printf("get one from minheap==>%d\n",minheap_fetch());
++i;
}
getchar();getchar();getchar();
}

# re: 我所理解的堆排序算法  回复  更多评论   

2007-03-31 08:55 by OK
@李伟
你这写的没有什么重用性!

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理