堆排序_堆排序java - CSDN
堆排序 订阅
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 展开全文
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
信息
外文名
Heapsort
发明人
罗伯特·弗洛伊德
类    别
排序算法
中文名
堆排序
起源于
罗伯特·弗洛伊德
堆排序简介
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 [1] 
收起全文
精华内容
参与话题
  • 堆排序原理及算法实现(最大堆)

    万次阅读 多人点赞 2012-05-15 22:24:15
    堆排序  堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。 1.堆  堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:  Key[i]=Key[2i+1]&&key>=key[2i+2]  即任何一非叶节点的关键字不大于...
    堆排序
    

           堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。

    1.堆

      堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:

      Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]

      即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

      堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的,小顶堆的堆顶的关键字是所有关键字中最小的。

    2.堆排序的思想

       利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。

        其基本思想为(大顶堆):

        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]同该区间的最后一个记录交换,然后将新的无序区调整为新的堆。

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

        下面举例说明:

         给定一个整形数组a[]={16,7,3,20,17,8},对其进行堆排序。

        首先根据该数组元素构建一个完全二叉树,得到

     
     然后需要构造初始堆,则从最后一个非叶节点开始调整,调整过程如下:

    20和16交换后导致16不满足堆的性质,因此需重新调整

    这样就得到了初始堆。

    即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质,因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。

    此时3位于堆顶不满堆的性质,则需调整继续调整

     这样整个区间便已经有序了。
        从上述过程可知,堆排序其实也是一种选择排序,是一种树形选择排序。只不过直接选择排序中,为了从R[1...n]中选择最大记录,需比较n-1次,然后从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过,而树形选择排序恰好利用树形的特点保存了部分前面的比较结果,因此可以减少比较次数。对于n个关键字序列,最坏情况下每个节点需比较log2(n)次,因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序,不适合记录较少的排序。
     
    测试程序
    复制代码
    /*堆排序(大顶堆) 2011.9.14*/ 
    
    #include <iostream>
    #include<algorithm>
    using namespace std;
    
    void HeapAdjust(int *a,int i,int size)  //调整堆 
    {
        int lchild=2*i;       //i的左孩子节点序号 
        int rchild=2*i+1;     //i的右孩子节点序号 
        int max=i;            //临时变量 
        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)
            {
                swap(a[i],a[max]);
                HeapAdjust(a,max,size);    //避免调整之后以max为父节点的子树不是堆 
            }
        }        
    }
    
    void BuildHeap(int *a,int size)    //建立堆 
    {
        int i;
        for(i=size/2;i>=1;i--)    //非叶节点最大序号值为size/2 
        {
            HeapAdjust(a,i,size);    
        }    
    } 
    
    void HeapSort(int *a,int size)    //堆排序 
    {
        int i;
        BuildHeap(a,size);
        for(i=size;i>=1;i--)
        {
            //cout<<a[1]<<" ";
            swap(a[1],a[i]);           //交换堆顶和最后一个元素,即每次将剩余元素中的最大者放到最后面 
              //BuildHeap(a,i-1);        //将余下元素重新建立为大顶堆 
              HeapAdjust(a,1,i-1);      //重新调整堆顶节点成为大顶堆
        }
    } 
    
    int main(int argc, char *argv[])
    {
         //int a[]={0,16,20,3,11,17,8};
        int a[100];
        int size;
        while(scanf("%d",&size)==1&&size>0)
        {
            int i;
            for(i=1;i<=size;i++)
                cin>>a[i];
            HeapSort(a,size);
            for(i=1;i<=size;i++)
                cout<<a[i]<<" ";
            cout<<endl;
        }
        return 0;
    }
    复制代码

    展开全文
  • 堆排序算法(图解详细流程)

    万次阅读 多人点赞 2019-04-16 09:04:40
    堆排序的时间复杂度O(N*logN),额外空间复杂度O(1),是一个不稳定性的排序 目录 一 准备知识 1.1 大根堆和小根堆 二 堆排序基本步骤 2.1 构造堆 2.2固定最大值再构造堆 三 总结 四代码 一 准备知识 堆的...

    堆排序的时间复杂度O(N*logN),额外空间复杂度O(1),是一个不稳定性的排序

    目录

    一 准备知识

    1.1  大根堆和小根堆

    二 堆排序基本步骤

    2.1 构造堆

    2.2 固定最大值再构造堆

    三 总结

    四 代码

     


    一 准备知识

    的结构可以分为大根堆和小根堆,是一个完全二叉树,而堆排序是根据的这种数据结构设计的一种排序,下面先来看看什么是大根堆和小根堆

    1.1  大根堆和小根堆

    性质:每个结点的值都大于其左孩子和右孩子结点的值,称之为大根堆;每个结点的值都小于其左孩子和右孩子结点的值,称之为小根堆。如下图

     我们对上面的图中每个数都进行了标记,上面的结构映射成数组就变成了下面这个样子

    还有一个基本概念:查找数组中某个数的父结点和左右孩子结点,比如已知索引为i的数,那么

    1.父结点索引:(i-1)/2(这里计算机中的除以2,省略掉小数)

    2.左孩子索引:2*i+1

    3.右孩子索引:2*i+2

    所以上面两个数组可以脑补成堆结构,因为他们满足堆的定义性质:

    大根堆:arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

    小根堆:arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

    二 堆排序基本步骤

    基本思想:

    1.首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端

    2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1

    3.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组

    2.1 构造堆

    将无序数组构造成一个大根堆(升序用大根堆,降序就用小根堆)

    假设存在以下数组

    主要思路:第一次保证0~0位置大根堆结构(废话),第二次保证0~1位置大根堆结构,第三次保证0~2位置大根堆结构...直到保证0~n-1位置大根堆结构(每次新插入的数据都与其父结点进行比较,如果插入的数比父结点大,则与父结点交换,否则一直向上交换,直到小于等于父结点,或者来到了顶端)

    插入6的时候,6大于他的父结点3,即arr(1)>arr(0),则交换;此时,保证了0~1位置是大根堆结构,如下图:

                                         (友情提示:待交换的数为蓝色,交换后的数为绿色)

     插入8的时候,8大于其父结点6,即arr(2)>arr(0),则交换;此时,保证了0~2位置是大根堆结构,如下图

    插入5的时候,5大于其父结点3,则交换,交换之后,5又发现比8小,所以不交换;此时,保证了0~3位置大根堆结构,如下图 

    插入7的时候,7大于其父结点5,则交换,交换之后,7又发现比8小,所以不交换;此时整个数组已经是大根堆结构 

     

    2.2 固定最大值再构造堆

    此时,我们已经得到一个大根堆,下面将顶端的数与最后一位数交换,然后将剩余的数再构造成一个大根堆

                                        (友情提示:黑色的为固定好的数字,不再参与排序) 

     此时最大数8已经来到末尾,则固定不动,后面只需要对顶端的数据进行操作即可,拿顶端的数与其左右孩子较大的数进行比较,如果顶端的数大于其左右孩子较大的数,则停止,如果顶端的数小于其左右孩子较大的数,则交换,然后继续与下面的孩子进行比较

    下图中,5的左右孩子中,左孩子7比右孩子6大,则5与7进行比较,发现5<7,则交换;交换后,发现5已经大于他的左孩子,说明剩余的数已经构成大根堆,后面就是重复固定最大值,然后构造大根堆

    如下图:顶端数7与末尾数3进行交换,固定好7,

    剩余的数开始构造大根堆 ,然后顶端数与末尾数交换,固定最大值再构造大根堆,重复执行上面的操作,最终会得到有序数组

     

    三 总结

    到这里,大家应该对堆排序都有了自己的见解,我们对上面的流程总结下:

    1、首先将无需数组构造成一个大根堆(新插入的数据与其父结点比较)

    2、固定一个最大值,将剩余的数重新构造成一个大根堆,重复这样的过程

    四 代码

    代码中主要两个方法:

    1、将待排序数组构造成一个大根堆(元素上升)

    2、固定一个最大值,将剩余的数再构造成一个大根堆(元素下降)

        //堆排序
        public static void heapSort(int[] arr) {
            //构造大根堆
            heapInsert(arr);
            int size = arr.length;
            while (size > 1) {
                //固定最大值
                swap(arr, 0, size - 1);
                size--;
                //构造大根堆
                heapify(arr, 0, size);
    
            }
    
        }
    
        //构造大根堆(通过新插入的数上升)
        public static void heapInsert(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                //当前插入的索引
                int currentIndex = i;
                //父结点索引
                int fatherIndex = (currentIndex - 1) / 2;
                //如果当前插入的值大于其父结点的值,则交换值,并且将索引指向父结点
                //然后继续和上面的父结点值比较,直到不大于父结点,则退出循环
                while (arr[currentIndex] > arr[fatherIndex]) {
                    //交换当前结点与父结点的值
                    swap(arr, currentIndex, fatherIndex);
                    //将当前索引指向父索引
                    currentIndex = fatherIndex;
                    //重新计算当前索引的父索引
                    fatherIndex = (currentIndex - 1) / 2;
                }
            }
        }
        //将剩余的数构造成大根堆(通过顶端的数下降)
        public static void heapify(int[] arr, int index, int size) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            while (left < size) {
                int largestIndex;
                //判断孩子中较大的值的索引(要确保右孩子在size范围之内)
                if (arr[left] < arr[right] && right < size) {
                    largestIndex = right;
                } else {
                    largestIndex = left;
                }
                //比较父结点的值与孩子中较大的值,并确定最大值的索引
                if (arr[index] > arr[largestIndex]) {
                    largestIndex = index;
                }
                //如果父结点索引是最大值的索引,那已经是大根堆了,则退出循环
                if (index == largestIndex) {
                    break;
                }
                //父结点不是最大值,与孩子中较大的值交换
                swap(arr, largestIndex, index);
                //将索引指向孩子中较大的值的索引
                index = largestIndex;
                //重新计算交换之后的孩子的索引
                left = 2 * index + 1;
                right = 2 * index + 2;
            }
    
        }
        //交换数组中两个元素的值
        public static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

                                                                  友情提示:手机观看,可以左右滑动 

     

     

     

    展开全文
  • 堆排序

    万次阅读 多人点赞 2019-06-20 17:38:19
    1、首先了解是什么 是一种数据结构,一种叫做完全二叉树的数据结构。 2、的性质 这里我们用到两种,其实也算是一种。 大顶堆:每个节点的值都大于或者等于它的左右子节点的值。 小顶堆:每个节点的值都...

    1、首先了解堆是什么

    堆是一种数据结构,一种叫做完全二叉树的数据结构。

    2、堆的性质

    这里我们用到两种堆,其实也算是一种。

    大顶堆:每个节点的值都大于或者等于它的左右子节点的值。

    小顶堆:每个节点的值都小于或者等于它的左右子节点的值。

    如上所示,就是两种堆。

    如果我们把这种逻辑结构映射到数组中,就是下边这样

    9 5 8 2 3 4 7 1
    1 3 5 4 2 8 9 7

    这个数组arr逻辑上就是一个堆。

    从这里我们可以得出以下性质(重点)

    对于大顶堆:arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

    对于小顶堆:arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

    3、堆排序的基本思想

    了解了以上内容,我们可以开始探究堆排序的基本思想了。

    堆排序的基本思想是:1、将带排序的序列构造成一个大顶堆,根据大顶堆的性质,当前堆的根节点(堆顶)就是序列中最大的元素;2、将堆顶元素和最后一个元素交换,然后将剩下的节点重新构造成一个大顶堆;3、重复步骤2,如此反复,从第一次构建大顶堆开始,每一次构建,我们都能获得一个序列的最大值,然后把它放到大顶堆的尾部。最后,就得到一个有序的序列了。

    假设给定的无序序列arr是:

    4 5 8 2 3 9 7 1

    1、将无序序列构建成一个大顶堆。

    首先我们将现在的无序序列看成一个堆结构,一个没有规则的二叉树,将序列里的值按照从上往下,从左到右依次填充到二叉树中。

     

    根据大顶堆的性质,每个节点的值都大于或者等于它的左右子节点的值。所以我们需要找到所有包含子节点的节点,也就是非叶子节点,然后调整他们的父子关系,非叶子节点遍历的顺序应该是从下往上,这比从上往下的顺序遍历次数少很多,因为,大顶堆的性质要求父节点的值要大于或者等于子节点的值,如果从上往下遍历,当某个节点即是父节点又是子节点并且它的子节点仍然有子节点的时候,因为子节点还没有遍历到,所以子节点不符合大顶堆性质,当子节点调整后,必然会影响其父节点需要二次调整。但是从下往上的方式不需要考虑父节点,因为当前节点调整完之后,当前节点必然比它的所有子节点都大,所以,只会影响到子节点二次调整。相比之下,从下往上的遍历方式比从上往下的方式少了父节点的二次调整。

    那么,该如何知道最后一个非叶子节点的位置,也就是索引值?

    对于一个完全二叉树,在填满的情况下(非叶子节点都有两个子节点),每一层的元素个数是上一层的二倍,根节点数量是1,所以最后一层的节点数量,一定是之前所有层节点总数+1,所以,我们能找到最后一层的第一个节点的索引,即节点总数/2(根节点索引为0),这也就是第一个叶子节点,所以第一个非叶子节点的索引就是第一个叶子结点的索引-1。那么对于填不满的二叉树呢?这个计算方式仍然适用,当我们从上往下,从左往右填充二叉树的过程中,第一个叶子节点,一定是序列长度/2,所以第一个非叶子节点的索引就是arr.length / 2 -1。

    现在找到了最后一个非叶子节点,即元素值为2的节点,比较它的左右节点的值,是否比他大,如果大就换位置。这里因为1<2,所以,不需要任何操作,继续比较下一个,即元素值为8的节点,它的左节点值为9比它本身大,所以需要交换

    交换后的序列为:

    4 5 9 2 3 8 7 1

    因为元素8没有子节点,所以继续比较下一个非叶子节点,元素值为5的节点,它的两个子节点值都比本身小,不需要调整;然后是元素值为4的节点,也就是根节点,因为9>4,所以需要调整位置

    交换后的序列为:

    9 5 4 2 3 8 7 1

    此时,原来元素值为9的节点值变成4了,而且它本身有两个子节点,所以,这时需要再次调整该节点

    交换后的序列为:

    9 5 8 2 3 4 7 1

    到此,大顶堆就构建完毕了。满足大顶堆的性质。

    2、排序序列,将堆顶的元素值和尾部的元素交换

    交换后的序列为:

    1 5 8 2 3 4 7 9

    然后将剩余的元素重新构建大顶堆,其实就是调整根节点以及其调整后影响的子节点,因为其他节点之前已经满足大顶堆性质。

    交换后的序列为:

    8 5 7 2 3 4 1 9

    然后,继续交换,堆顶节点元素值为8与当前尾部节点元素值为1的进行交换

    交换后的序列为:

    1 5 7 2 3 4 8 9

    重新构建大顶堆

    交换后的序列为:

    7 5 4 2 3 1 8 9

    继续交换

    交换后的序列为:

    1 5 4 2 3 7 8 9

    重新构建大顶堆

    构建后的序列为:

    5 3 4 2 1 7 8 9

    继续交换

    交换后的序列为:

    1 3 4 2 5 7 8 9

    重新构建大顶堆

    构建后的序列为:

    4 3 1 2 5 7 8 9

    继续交换

    交换后的序列为:

    2 3 1 4 5 7 8 9

    重新构建大顶堆

    构建后的序列为:

    3 2 1 4 5 7 8 9

    继续交换

    交换后的序列为:

    1 2 3 4 5 7 8 9

    重新构建大顶堆

    构建后的序列为:

    2 1 3 4 5 7 8 9

    继续交换

    交换后的序列为:

    1 2 3 4 5 7 8 9

    此时,序列排序完成。以上就是整个堆排序的逻辑。

    4、堆排序的代码实现(java版本)

    public class HeapSort {
    
    	public static void heapSort(int[] arr) {
    		if (arr == null || arr.length == 0) {
    			return;
    		}
    		int len = arr.length;
    		// 构建大顶堆,这里其实就是把待排序序列,变成一个大顶堆结构的数组
    		buildMaxHeap(arr, len);
    
    		// 交换堆顶和当前末尾的节点,重置大顶堆
    		for (int i = len - 1; i > 0; i--) {
    			swap(arr, 0, i);
    			len--;
    			heapify(arr, 0, len);
    		}
    	}
    
    	private static void buildMaxHeap(int[] arr, int len) {
    		// 从最后一个非叶节点开始向前遍历,调整节点性质,使之成为大顶堆
    		for (int i = (int)Math.floor(len / 2) - 1; i >= 0; i--) {
    			heapify(arr, i, len);
    		}
    	}
    
    	private static void heapify(int[] arr, int i, int len) {
    		// 先根据堆性质,找出它左右节点的索引
    		int left = 2 * i + 1;
    		int right = 2 * i + 2;
    		// 默认当前节点(父节点)是最大值。
    		int largestIndex = i;
    		if (left < len && arr[left] > arr[largestIndex]) {
    			// 如果有左节点,并且左节点的值更大,更新最大值的索引
    			largestIndex = left;
    		}
    		if (right < len && arr[right] > arr[largestIndex]) {
    			// 如果有右节点,并且右节点的值更大,更新最大值的索引
    			largestIndex = right;
    		}
    
    		if (largestIndex != i) {
    			// 如果最大值不是当前非叶子节点的值,那么就把当前节点和最大值的子节点值互换
    			swap(arr, i, largestIndex);
    			// 因为互换之后,子节点的值变了,如果该子节点也有自己的子节点,仍需要再次调整。
    			heapify(arr, largestIndex, len);
    		}
    	}
    
    	private static void swap (int[] arr, int i, int j) {
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    }

    5、复杂度分析

    因为堆排序无关乎初始序列是否已经排序已经排序的状态,始终有两部分过程,构建初始的大顶堆的过程时间复杂度为O(n),交换及重建大顶堆的过程中,需要交换n-1次,重建大顶堆的过程根据完全二叉树的性质,[log2(n-1),log2(n-2)...1]逐步递减,近似为nlogn。所以它最好和最坏的情况时间复杂度都是O(nlogn),空间复杂度O(1)。

    展开全文
  • 白话经典算法系列之七 堆与堆排序

    万次阅读 多人点赞 2012-11-09 18:17:53
    堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。二叉堆的定义二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性:1.父...
     堆排序快速排序归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。

    二叉堆的定义

    二叉堆是完全二叉树或者是近似完全二叉树。

    二叉堆满足二个特性:

    1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。

    2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

    当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆:

    由于其它几种堆(二项式堆,斐波纳契堆等)用的较少,一般将二叉堆就简称为堆。

    堆的存储

    一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

    堆的操作——插入删除

    下面先给出《数据结构C++语言描述》中最小堆的建立插入删除的图解,再给出本人的实现代码,最好是先看明白图后再去看代码。

    堆的插入

    每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列,现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中,对照《白话经典算法系列之二 直接插入排序的三种实现》不难写出插入一个新数据时堆的调整代码:

    //  新加入i结点  其父结点为(i - 1) / 2
    void MinHeapFixup(int a[], int i)
    {
        int j, temp;
    	
    	temp = a[i];
    	j = (i - 1) / 2;      //父结点
    	while (j >= 0 && i != 0)
    	{
    		if (a[j] <= temp)
    			break;
    		
    		a[i] = a[j];     //把较大的子结点往下移动,替换它的子结点
    		i = j;
    		j = (i - 1) / 2;
    	}
    	a[i] = temp;
    }

    更简短的表达为:

    void MinHeapFixup(int a[], int i)
    {
    	for (int j = (i - 1) / 2; (j >= 0 && i != 0)&& a[i] > a[j]; i = j, j = (i - 1) / 2)
    		Swap(a[i], a[j]);
    }

    插入时:

    //在最小堆中加入新的数据nNum
    void MinHeapAddNumber(int a[], int n, int nNum)
    {
    	a[n] = nNum;
    	MinHeapFixup(a, n);
    }

    堆的删除

    按定义,堆中每次都只能删除第0个数据。为了便于重建堆,实际的操作是将最后一个数据的值赋给根结点,然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的,如果父结点比这个最小的子结点还小说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。下面给出代码:

    //  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
    void MinHeapFixdown(int a[], int i, int n)
    {
        int j, temp;
    
    	temp = a[i];
    	j = 2 * i + 1;
    	while (j < n)
    	{
    		if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的
    			j++;
    
    		if (a[j] >= temp)
    			break;
    
    		a[i] = a[j];     //把较小的子结点往上移动,替换它的父结点
    		i = j;
    		j = 2 * i + 1;
    	}
    	a[i] = temp;
    }
    //在最小堆中删除数
    void MinHeapDeleteNumber(int a[], int n)
    {
    	Swap(a[0], a[n - 1]);
    	MinHeapFixdown(a, 0, n - 1);
    }

    堆化数组

    有了堆的插入和删除后,再考虑下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吧,不用!先看一个数组,如下图:

    很明显,对叶子结点来说,可以认为它已经是一个合法的堆了即20,60, 65, 4, 49都分别是一个合法的堆。只要从A[4]=50开始向下调整就可以了。然后再取A[3]=30,A[2] = 17,A[1] = 12,A[0] = 9分别作一次向下调整操作就可以了。下图展示了这些步骤:

    写出堆化数组的代码:

    //建立最小堆
    void MakeMinHeap(int a[], int n)
    {
    	for (int i = n / 2 - 1; i >= 0; i--)
    		MinHeapFixdown(a, i, n);
    }
    


    至此,堆的操作就全部完成了(注1),再来看下如何用堆这种数据结构来进行排序。

    堆排序

    首先可以看到堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据,重复上述步骤直至堆中只有一个数据时就直接取出这个数据。

    由于堆也是用数组模拟的,故堆化数组后,第一次将A[0]与A[n - 1]交换,再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换,再对A[0…n - 3]重新恢复堆,重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间,故操作完成后整个数组就有序了。有点类似于直接选择排序

    void MinheapsortTodescendarray(int a[], int n)
    {
    	for (int i = n - 1; i >= 1; i--)
    	{
    		Swap(a[i], a[0]);
    		MinHeapFixdown(a, 0, i);
    	}
    }

    注意使用最小堆排序后是递减数组,要得到递增数组,可以使用最大堆。

    由于每次重新恢复堆的时间复杂度为O(logN),共N - 1次重新恢复堆操作,再加上前面建立堆时N / 2次向下调整,每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)。STL也实现了堆的相关函数,可以参阅《STL系列之四 heap 堆》。

     

     

    注1 作为一个数据结构,最好用类将其数据和方法封装起来,这样即便于操作,也便于理解。此外,除了堆排序要使用堆,另外还有很多场合可以使用堆来方便和高效的处理数据,以后会一一介绍。

     

     

    转载请标明出处,原文地址:http://blog.csdn.net/morewindows/article/details/6709644

    展开全文
  • 堆排序算法详解

    万次阅读 多人点赞 2018-10-14 22:12:03
    一、堆排序算法原理和动态图解  将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新...
  • 堆支持的操作① 往堆中插入一个元素② 删除堆顶元素Ⅳ 堆排序A. 建堆B. 排序Ⅴ 堆排序与快速排序的比较 Ⅰ 前言 在前面的文章里,我讲了树、二叉树以及二叉树的特殊形式。这篇文章,我们再来看看另外一种特殊的树...
  • 排序算法之python堆排序

    千次阅读 2019-03-20 16:29:31
    堆排序 介绍: 堆排序也是一种选择排序。个人觉得是简单选择排序的优化,借助于二叉树这种数据结构,每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。跟简单...
  • 开门见山,本文讲述堆排序。 就我自身对于排序的了解来看,其实堆排序是诸多排序中最难写的,光是理解起来都有点费劲,本文旨在于用通俗易懂的话,把堆排序娓娓道来。 下面,开始! 1:堆 毫无疑问,排序两个字...
  • 堆排序(大堆)

    千次阅读 2018-05-08 08:25:04
    前言:堆排序可分为大堆和小堆。 其实堆的空间结构实际上就是一棵完全二叉树,不过堆有它自己的限定条件。大堆就是树中每个父亲节点都要比孩子节点大,并且两个兄弟之间是没有大小区分的。小堆与之相反,就是每个...
  • 数据结构示例——堆排序过程

    万次阅读 多人点赞 2015-12-14 15:43:15
    完整算法见[例程],本文用一个例子,演示堆排序的过程。例:对{57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7}进行堆排序的过程。算法如下:void HeapSort(RecType R[],int n) { int i; RecType temp; //(1)循环...
  • 排序算法(三)堆排序原理与实现(小顶堆)

    万次阅读 多人点赞 2017-05-19 09:04:03
    堆排序实际上是利用堆的性质来进行排序的,要知道堆排序的原理我们首先一定要知道什么是堆。 堆的定义: 堆实际上是一棵完全二叉树。 堆满足两个性质: 1、堆的每一个父节点都大于(或小于)其子节点; 2、堆的...
  • 我的机器学习教程「美团」算法工程师带你入门机器学习 已经开始更新了,欢迎大家订阅~ 任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习小组“,沙雕博主在线答疑...
  • 排序算法之堆排序(Heap Sort)——C语言实现

    万次阅读 多人点赞 2018-08-21 16:44:21
    堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。 算法分析 在学习堆排序之前我们要先了解堆这种数据结构。 堆的定义如下:n个元素的序列{k1,k2,···,kn}当且...
  • 下面是建立大根的代码 template void CreateBigRootHeap(Type *array, int len) { int i, j, k; Type temp; for (i = (len - 1) / 2; i >= 0; --i) { temp = array[i]; k = i;
  • 二叉排序树和的区别

    万次阅读 多人点赞 2015-11-20 12:37:04
    在二叉排序树中,每个结点的值均大于其左子树上所有结点的值,小于其右子树上所有结点的值,对二叉排序树进行中序遍历得到一个有序序列。所以,二叉排序树是结点之间满足一定次序关系的二叉树;  是一个完全...
  • 这两天看了一下常见的三种排序算法:堆排序、快速排序、gong
  • 【排序算法】堆排序原理及Java实现

    万次阅读 多人点赞 2016-04-27 18:47:37
    堆排序就是利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是,将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是...
  • 堆排序算法之初始堆建立

    千次阅读 2019-07-01 20:47:54
    以大顶堆为例(初始建操作复杂度是 O(n)) 1.首先根据序列构建一个完全二叉树 2.在完全二叉树的基础上,从最后一个非叶结点开始调整:比较三个元素的大小–自己,它的左孩子,右孩子。分为三种情况: 自己最大,不用...
  • 为什么说快速排序是性能最好的排序算法?

    万次阅读 多人点赞 2018-09-12 22:47:41
    刚刚学习了排序这一章,看到了书中...其实经过实验,会发现相同的数据规模,快速排序比堆排序的效率高很多,并且随着数据规模的扩大,二者的差距不断扩大,快速排序的优势越来越明显。快速排序的时间复杂度近似线性...
  • 快速排序和堆排序的使用场景比较

    千次阅读 2016-12-16 15:35:03
    快速排序 是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο (n log n)次比较。在最坏状况下则需要 Ο (n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο (n log...
1 2 3 4 5 ... 20
收藏数 242,256
精华内容 96,902
关键字:

堆排序