【408数据结构与算法】—堆排序（二十一）

【408数据结构与算法】—堆排序（二十一）

一、堆的定义

从堆的定义可以看出，堆实质是满足如下性质的完全二叉树，二叉树中任一非叶子结点均小于（大于）它的孩子结点

C语言代码实现

#include 
#include 
void HeapAdjust(int a[],int s,int m)//一次筛选的过程
{
    int rc,j;
    rc=a[s];
    for(j=2*s;j<=m;j=j*2)//通过循环沿较大的孩子结点向下筛选
    {
        if(j<m&&a[j]<a[j+1]) j++;//j为较大的记录的下标
        if(rc>a[j]) break;
        a[s]=a[j];s=j;
    }
    a[s]=rc;//插入
}
void HeapSort(int a[],int n)
{
    int temp,i,j;
    for(i=n/2;i>0;i--)//通过循环初始化顶堆
    {
        HeapAdjust(a,i,n);
    }
    for(i=n;i>0;i--)
    {
        temp=a[1];
        a[1]=a[i];
        a[i]=temp;//将堆顶记录与未排序的最后一个记录交换
        HeapAdjust(a,1,i-1);//重新调整为顶堆
    }
}
int main()
{
    int n,i;
    scanf("%d",&n);
    int a[n+1];
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    HeapSort(a,n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

判断是否是堆?

二、堆排序

若在输出堆顶的最小值（最大值）后，使得剩余n-1 个元素的序列重新建成一个堆，则得到n个元素的次小值（次大值）如此反复，便能得到一个有序序列，这个过程称为堆排序

三、实现堆排序需要解决两个问题

（一）、如何在输出堆顶元素后，调整剩余元素为一个新的堆？

小根堆

• 输出堆顶元素之后，以堆中的最后一个元素替代
• 然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换
• 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为筛选。

堆的调整

筛选过程的算法描述为

从以上代码可以看出：对于一个无序序列反复筛选就可以得到一个堆即从一个无序序列建堆的过程就是一个反复筛选的过程

（二）、如何由一个无序序列建成一个堆？

😛堆的建立

• 显然单结点的二叉树是堆；
• 在完全二叉树中所有以子节点（序号i>n/2）为根的子树是堆

由于堆实质是一个线性表，那么我们可以顺序存储一个堆

例如：有关键字为49,38,65,97,76,13,27,49的一组记录，将其按关键字调整为一个小根堆


由以上分析知：

若一个无序序列建堆，然后输出根，重复该过程就可以由一个无序序列输出有序序列

实际上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。

堆排序算法

算法性能分析：

• 初始化时间不超过O(n)
  
• 堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上，堆排序在最坏的情况下，其时间复杂度为O(nlog2n),这是堆排序的最大优点。无论待排序列还是逆序排列，都不会使堆排序处于最好或最坏的状态。
• 另外，堆排序仅需一个记录大小交换用的辅助存储空间
• 然而堆排序是一种不稳定的排序方法，它不是适用于待排序记录个数 n较少的情况，但对于n较大的文件还是很有效的。