堆排序(HeapSort)

2020年02月19日 198点热度 1人点赞 1条评论

堆排序是利用堆的性质进行排序的排序方式,时间复杂度O (nlgn),空间复杂度O(1),是一种原地排序算法。

首先 你需要知道什么是树,什么是二叉树,以及什么是完全二叉树

堆是一种特殊的完全二叉树,堆分为大顶堆和小顶堆,大顶堆要求每个节点的子节点(如果有),必须小于父节点,整个树的根节点是最大的,小顶堆相反,每个子节点比父节点大,根节点是最小的节点。

我们以大顶堆为例,以下是几个大顶堆。

按顺序给第一个堆的每个节点编上号如下图

所以就可以用一个数组进行储存;

int arr[] = {10,5,7,3,4};

假如有以下堆

我们把它存到数组中

存到数组中有以下规律

完全二叉树规律

1.第i个节点的双亲节点(parent)为(i-1)/2

2.第i个节点的左孩子(child1,c1)为2*i+1

3.第i个节点的右孩子为(child2,c2)为2*i+2

算法步骤

1.将数组整理成堆

2.将根节点和最后一个节点交换

3.将最后一个节点(交换前为根节点)拿出,放到有序区

4.跳到第一步,直到堆空

说白了,其实这就是一个选择排序,只不过在未排序部分中挑选最大值(最小值)的方式的不同。

如何将数组整理成堆?

这里先把问题简化一下,我们假设,有一个用数组储存的完全二叉树,它的根节点和两个孩子节点三个节点构成的一个树不满足根节点小于孩子节点,往下层都满足父节点小于孩子节点,如下图。

我们找出前三个节点中的最大值——19,然后将父节点和这个最大的子节点交换:

然后我们再关注这个c1(左孩子)节点,将它与两个孩子节点比较,如果小于孩子节点就找出两个孩子里面最大的孩子节点,然后将父节点和这个节点交换,也就是值为i的节点和值为9的节点交换。如下图

 

最后当前值为1的节点没有子节点,调整完毕;写个函数叫heapify(堆化);

int heapify(int tree[],int n , int root)
 { 
    int max = root; 
    int c1 = root*2+1,c2 = root*2+2; 
    if(c1<n&&tree[c1]>tree[max]) 
    { 
        max=c1; 
    } 
    if(c2<n&&tree[c2]>tree[max]) 
    { 
    max=c2;
    } 
    if(max!= root)
    { 
        swap(max,root,tree); 
        heapify(tree,n,max);//let swaped node be heapified; 
    } 
}

 


好了,这样就能实现将一个除了根节点不满足堆的定义下面的子树都满足的一个树通过heapify将它调整成大顶堆,那如果给我们一个完全没有任何顺序的数组,该如何把它调整成堆? 

需要的就是倒序依次作为父节点进行heapify,如下图顺序

用代码表示就是

void buildHeap(int arr,int n)
{
    int i;
    for(i = (n-2)/2;i>=0;i--)
    {
        heapify(arr,n,i);
    }
}

好了能调整堆之后我们就能用堆进行排序了排序步骤

1.将数组调整为堆

2.将最顶端的根节点和最后一个节点(上面那个图的0和4)进行交换

3.将最后一个节点(交换前的根节点)给摘下来,放到已排序区

4.对这个摘除后的堆进行heapify(为什么不是buildHeap? 因为我们把最后一个节点放到根上之后,除根节点和他的两个子节点外,剩余部分符合父节点大于子节点的规律,如果忘了的话请跳到前面看buildHeap那一段)

用代码实现就是:

void heapSort(int arr,int n)
{
    int i;
    buildHeap(arr,n);
    for(i = n-1;i>=0;i--)
    {
        swap(0,i,arr);
        heapify(arr,i,0);
    }
}

C语言完整实现

最后附上全部的代码

#include<stdio.h>
void swap(int a,int b ,int arr[])
{
    int temp ;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] =temp;
    return ;
}
int heapify(int tree[],int n , int root)
{
    int max = root;
    int c1 = root*2+1,c2 = root*2+2;
    if(c1<n&&tree[c1]>tree[max])
    {
        max=c1;
    }
    if(c2<n&&tree[c2]>tree[max])
    {
        max=c2;
    }
    if(max!= root)
    {
        swap(max,root,tree);
        heapify(tree,n,max);//let swaped node be heapified;
    }
}
void buildHeap(int arr,int n)
{
    int i;
    for(i = (n-2)/2;i>=0;i--)
    {
        heapify(arr,n,i);
    }
}
void heapSort(int arr,int n)
{
    int i;
    buildHeap(arr,n);
    for(i = n-1;i>=0;i--)
    {
        swap(0,i,arr);
        heapify(arr,i,0);
    }
}
int main()
{
    int arr[100];
    int n = 10;
    for(int i = 0;i<n;i++)
    {
        scanf("%d",arr+i);
    }
    heapSort(arr,n);
    for(int i = 0;i<n;i++)
    {
        printf("%d",arr[i]);
    }
    return 0;
}

参考B站视频资料:

https://www.bilibili.com/video/av62952101/

https://www.bilibili.com/video/av47196993/

Danny

我就如一粒石子,在随波逐流中,逐渐冲蚀了自己的棱角,变光滑,也变丑陋。

文章评论

  • LeadDing

    ❤👍👍👍👍👍👍👍👍👍👍

    2020年02月19日