首页 > 其他 > 详细

堆排序算法

时间:2014-02-22 10:45:26      阅读:251      评论:0      收藏:0      [点我收藏+]

堆的概念:

最小值堆:最小值堆是一个关键码序列{K0,K1,…Kn-1},它具有如下特性:

  1. Ki≤K2i+1 (i=0,1,…, n/2-1)
  2. Ki≤K2i十2

最大值堆:最大值堆是一个关键码序列{K0,K1,…Kn-1},它具有如下特性:

  1. Ki≥K2i+1 (i=0,1,…, n/2-1)
  2. Ki≥K2i十2

一句话,堆就是具有下列性质的二叉树:树的每个节点的值都大于等于其左右孩子节点的值就是大顶堆;树的每个节点的值都小于等于其左右孩子节点的值就是小顶堆。

本文主要是想通过堆来进行排序,我们会提出一个疑问,我现在有一个堆,那么我按照层序遍历遍历这棵树的每个节点,输出的值是不是有序的呢?答案是否定的。一个堆,我们只保证每个节点与其子节点的关系,并不保证两个子节点的关系。不过我们可以肯定的是,大顶堆的根节点一定是整棵树中最大的值,小顶堆的根节点一定是整棵树中最小的值。

那么思路就出来了,我们可以把这个最大(小)值拿出来,重新再把剩余的节点建立成大(小)顶堆,那么我们就可以得到次大值的……一次类推,我们就可以得到一个有序的序列。

按照这个思路,我们必须要解决的问题就是怎么建立一个大(小)顶堆。

建立堆

首先有把n个将要被排序的关键码放到一棵完全二叉树的各个结点中(这时的完全二叉树并不具备堆的特性)。显然,所有i>(n-1)/2的结点Ki都没有子女结点,因此以这样的Ki为根的子树已经是堆。然后从i=(n-1)/2的结点Ki开始,逐步把以Ki(i<=(n-1)/2)为根的子树排成堆,直到以K0为根的子树排成堆,就完成了建堆过程。

这个建堆过程就是比较当前节点和其左右孩子节点的值的大小,找出这三个点的最大(小)值,把最大(小)值放在顶端,与当前值进行交换。那么我们就要保证交换之后的的子树还要满足堆的要求,这就需要重复上述检查排序过程即可(递归)。

具体的代码如下所示:

bubuko.com,布布扣
void swap(int *valA, int *valB)
{
    int temp=*valA;
    *valA=*valB;
    *valB=temp;
}
//左子结点
int left_child(int index)
{
    return 2*index+1;
}
//右子节点
int right_child(int index)
{
    return 2*index+2;
}
//调整堆
void heapify(int varArr[],int current,int end)
{
    int l=left_child(current),r=right_child(current);
    int largest;

    if (l<end&&varArr[current]<varArr[l])
        largest=l;
    else
        largest=current;

    if (r<end&&varArr[largest]<varArr[r])
        largest=r;

    if(largest!=current)
    {
        swap(&varArr[current],&varArr[largest]);
        heapify(varArr,largest,end);//递归调整子树成堆
    }
}
//建立一个堆
void bulid_init_heap(int varArr[],int heap_len)
{
    for (int i=(heap_len-2)/2;i>=0;i--)
    {
        heapify(varArr,i,heap_len);
    }
}
//堆排序算法
void heapSort(int varArr[],int heap_len)
{
    bulid_init_heap(varArr,heap_len);
    for (int i=heap_len-1;i>=0;i--)
    {
        swap(&varArr[i],&varArr[0]);//把已经找出来的最大值与堆里面最后一个值交换
        heapify(varArr,0,i);//把剩余的值重新建立成堆
    }
}

void print_arr(int *var_heap,int var_len)
{
    for (int i=0;i<var_len;i++)
    {
        printf("%d ",var_heap[i]);
    }
    printf("\n");
}

int main(){
    int var_heap[]={1,4,6,2,5,9,6,5,10};
    int var_len=sizeof(var_heap)/sizeof(int);
    heapSort(var_heap,var_len);
    print_arr(var_heap,var_len);
    return 0;
}
bubuko.com,布布扣

堆排序算法

原文:http://www.cnblogs.com/havePassed/p/3560126.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!