首页 > 代码库 > 堆排序——大根堆(大顶堆)

堆排序——大根堆(大顶堆)

2024-07-17 03:08:58   222人阅读

1.小根堆
若根节点存在左子女则根节点的值小于左子女的值；若根节点存在右子女则根节点的值小于右子女的值。
2.大根堆
若根节点存在左子女则根节点的值大于左子女的值；若根节点存在右子女则根节点的值大于右子女的值。
3.结论
（1）堆是一棵完全二叉树（如果公有h层，那么1~h-1层均满，在h层连续缺失若干个右叶子）。
（2）小根堆的根节点的值是最小值，大根堆的根节点的值是最大值。
（3）堆适合于采用顺序存储。
4.堆的插入算法
将一个数据元素插入到堆中，使之依然成为一个堆。
算法描述：先将结点插入到堆的尾部，再将该结点逐层向上调整，直到依然构成一个堆，调整方法是看每个子树是否符合大（小）根堆的特点，不符合的话则调整叶子和根的位置。
5.堆的删除算法
堆在删除元素时，只可以删除根节点。
算法描述：将根节点删除后用堆尾结点进行填补，调整二叉树，使之依然成为一个堆。
6.堆排序（大根堆，小根堆类似）
其基本思想为(大根堆)：
    1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区，构建的过程是每个非叶子结点都经过一次调整，调整顺序为从底层至顶层(调整过程中含有递归)，这样调整下来这个二叉树整体上就是一个大根堆(或小根堆)了;

    2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];

    3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
    操作过程如下：
     1)初始化堆：将R[1..n]构造为堆；

     2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。

    因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
操作过程图示：

    从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1...n]中选择最大记录，需比较n-1次，然后从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlog2(n)。堆排序为不稳定排序，不适合记录较少的排序。
关于log2(n)的理解：根据堆排序的过程，每次将大根堆根节点的值跟最后一个叶子的值进行交换，那如果最后的叶子结点正好是最小的数，那么这个叶子结点就会一层层的被放到子树最终放到叶子结点的位子（不是前面的叶子结点的位置了），这样的话这个叶子结点经过的层数就刚好为log2(n)。然而其他没有交换的二叉树的分支，因为以前都是大根堆，所以大根堆的性质还是没有变化，这一点对理解程序至关重要。C语言程序如下：
/*堆排序(大根堆)*/ 
#include <stdio.h>

/*注意：这个函数只会在调整被交换的位置为大根堆，未交换的分支不会处理，
所以不能将一个非大根堆二叉树的根结点传递过来让这个函数将其处理为大根堆*/
void heap_ajust(int *a, int i, int size)  /*a为堆存储数组，size为堆的大小*/
{
    int lchild = 2*i;       //i的左孩子节点序号 
    int rchild = 2*i +1;     //i的右孩子节点序号 
    int max = i; /*存放三个顶点中最大的数的下标*/
	int temp;
    if(i <= size/2)          //如果i是叶节点就不用进行调整 
    {
        if(lchild<=size && a[lchild]>a[max])
        {
            max = lchild;
        }    
        if(rchild<=size && a[rchild]>a[max])
        {
            max = rchild;
        }
        if(max != i)
        {
            temp = a[i]; /*交换a[i]和a[max]的值*/
			a[i] = a[max];
			a[max] = temp;
            heap_ajust(a, max, size); /*被交换的位置以前是大根堆，现在可能不是大根堆
			                            所以需要重新调整使其成为大根堆结构*/ 
        }
    }        
}

void build_bheap(int *a, int size) /*建立大根堆*/ 
{
    int i;
    for(i=size/2; i >= 1; i--) /*非叶节点最大序号值为size/2*/
    {
        heap_ajust(a, i, size); /*每个非叶子结点都需要调用这个函数*/   
    }    
} 

void heap_sort(int *a, int size) /*堆排序*/ 
{
    int i;
	int temp;

    build_bheap(a, size);
    for(i=size; i >= 1; i--)
    {
        temp = a[1];
		a[1] = a[i];
		a[i] = temp; /*交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面*/ 
        heap_ajust(a, 1, i-1); /*重新调整堆顶节点成为大顶堆，只有被交换的分支才有可能不是大根堆*/
    }
} 

int main(int argc, char *argv[])
{
    int a[]={0,16,20,3,11,17,8};
    int size = sizeof(a)/sizeof(int) -1;
	int i;

	printf("size = %d\n", size);
    heap_sort(a, size);
	printf("Sort over:"); 
    for(i=1;i <= size; i++)
        printf("%d ", a[i]);
    printf("\n");

    return 0;
}
程序运行截图为：

参考博文地址：http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html


联系
我们