精华内容
下载资源
问答
  • 则利用堆排序的方法
    千次阅读
    2022-02-05 23:54:50

    什么是堆

    堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

    • 大顶堆:每个结点的值都大于或等于左右子结点的值
    • 小顶堆:每个结点的值都小于或等于左右子结点的值

    在这里插入图片描述

    堆排序

    堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    思路分析

    1、将待排序的序列构造成一个大顶堆(升序大顶堆降序小顶堆)
    在这里插入图片描述
    2、将堆顶元素(根结点)和末尾元素进行互换。然后将剩余n-1个元素重新构造一个新的大顶堆
    在这里插入图片描述
    3、重复进行第2步操作便能得到一个有序的序列

    代码实现

    在这说明下面代码中的一个问题:为什么从arr.length/2-1开始?
    由于堆排序近似完全二叉树假设最后一个非叶子结点下标为n
    当它的左子结点为末尾元素时:2n+1 = length-1 ==> n = length/2-1
    当它的右子结点为末尾元素时:2
    n+2 = length-1 ==> n = length/2-(3/2)
    在计算机中3/2是等于1的,所以从arr.length/2-1
    可以在写代码之前看看这篇文章:二叉树顺序存储

    import java.util.Arrays;
    public class HeapSort {
    
        public static void main(String[] args) {
            int[] array = {4,6,1,2,9,8,3,5};
            heapSort(array);
            System.out.println(Arrays.toString(array));
        }
    
        /**
         * 堆排序
         */
        public static void heapSort(int[] arr){
            //为什么从arr.length/2-1开始?
            for (int i = arr.length/2-1; i >= 0 ; i--) {
                adjustHeap(arr,i,arr.length);
            }
    
            for (int j = arr.length-1; j > 0; j--) {
                int temp = arr[j];
                arr[j] = arr[0];
                arr[0] = temp;
                /*为什么从0开始?
                    因为在第一次构建大顶堆后让堆顶元素和末尾元素进行交换
                    而对于其他的非叶子结点所对应的子树都是大顶堆就无需调整,
                    只需要堆顶元素(下标为0的非叶子结点)的子树调整成大顶堆
                */
                adjustHeap(arr,0,j);
    
            }
        }
    
        /**
         * 构建大顶堆
         * 注意:
         *      这个方法并不是将整个树调整成大顶堆
         *      而是以i对应的非叶子结点的子树调整成大顶堆
         * @param arr 待调整的数组
         * @param i 非叶子结点在数组中的索引(下标)
         * @param length 进行调整的元素的个数,length是在逐渐减少的
         */
        public static void adjustHeap (int[] arr,int i,int length){
            /*取出当前非叶子结点的值保到临时变量中*/
            int temp = arr[i];
    
            /*j=i*2+1表示的是i结点的左子结点*/
            for (int j = i * 2 + 1; j < length ; j = j * 2 + 1) {
                if (j+1 < length && arr[j] < arr[j+1]){ //左子结点小于右子结点
                    j++; //j指向右子结点
                }
                if (arr[j] > temp){ //子节点大于父节点
                    arr[i] = arr[j]; //把较大的值赋值给父节点
                    //arr[j] = temp; 这里没必要换
                    i = j; //让i指向与其换位的子结点 因为
                }else{
                    /*子树已经是大顶堆了*/
                    break;
                }
            }
            arr[i] = temp;
        }
    }
    

    运行结果

    [1, 2, 3, 4, 5, 6, 8, 9]
    
    Process finished with exit code 0
    
    更多相关内容
  • 堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素。...
  • 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序的平均时间复杂度为Ο...
  • 用一句概括,堆排序就是一种改进的选择排序,改进的地方在于,每次做选择的时候,不单单把最大的数字选择出来,而且把排序过程中的一些操作进行了记录,这样在后续排序中可以利用,并且有分组的思想在里面,从而提高...
  • 堆排序(Heap Sort)就是利用堆进行排序的方法。他的基本思想是,将待排序的序列构造成一个大顶堆,此时,整个序列的最大值就是对定的根节点。将他移走(其实就是将其余对数组的末尾元素交换,此时末尾元素就是最大...
  • 堆排序算法

    千次阅读 2021-02-05 13:43:18
    堆排序利用堆数据结构而设计的一种排序算法,堆排序是一种选择排序,其最坏,最好,平均时间复杂度均为O(nlogn),同时也是不稳定排序。 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的...

    一、堆排序算法基本思想

    堆排序是利用堆数据结构而设计的一种排序算法,堆排序是一种选择排序,其最坏,最好,平均时间复杂度均为O(nlogn),同时也是不稳定排序
    堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 如下图所示,其中大顶堆的性质**:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]**
    在这里插入图片描述
    每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆,如下图所示,其中小顶堆性质:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
    在这里插入图片描述

    注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系

    堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,即可得到一个有序序列。

    二、堆排序图解
    在这里插入图片描述
    三、实现思路

    (1)将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
    (2)将堆顶元素与末尾元素交换,将最大元素放到数组末端;
    (3)重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

    E.g:
    1、将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆
    (1)假设给定无序序列结构如下:

    在这里插入图片描述
    (2)此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1=5/2-1=1,即下面的6结点),从右至左,从下至上进行调整。

    在这里插入图片描述
    (3)找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换。
    在这里插入图片描述
    (4)此时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。
    在这里插入图片描述
    2、将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。
    (1)将堆顶元素9和末尾元素4进行交换。
    在这里插入图片描述
    (2)重新调整结构,使其继续满足堆定义。
    在这里插入图片描述
    (3)再将堆顶元素8与末尾元素5进行交换,得到第二大元素8。
    在这里插入图片描述
    (4)后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序。
    在这里插入图片描述

    四、代码实现

    1、大顶堆

    package Sort;
    
    import java.util.Arrays;
    
    public class HeapSort {
    	//调整大顶堆
    	/**
    	 * @param arr     待调整数组
    	 * @param i       非叶子结点在数组中的索引
    	 * @param length  调整元素个数(length在逐渐减少)
    	 */
    	public static void adjustHeap(int[] arr, int i, int length) {
    		int temp = arr[i];//取出当前元素i
    		for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始,即2i+1处开始
    			if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点,则k指向右子结点(arr[k]表示左子结点,arr[k+1]表示右子结点)
    				k++;
    			}
    			if (arr[k] > temp) {//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
    				arr[i] = arr[k];
    				i = k;//i指向k,即将较小值放在较大值下方
    			} else {
    				break;//我们是自下而上进行调整即可保证下方子树已为大顶堆
    			}
    		}//当for循环结束后,我们将以i为父结点的树的最大值放在局部堆顶
    		arr[i] = temp;//将temp值放到调整后的位置
    	}
    	
    	public static  void swap(int[] arr,int a,int b) {//交换元素
    		int temp=arr[a]; 
    		arr[a]=arr[b];
    		arr[b]=temp;
    	}
    	
    	public static void heapsort(int[] arr) {
    		for(int i=arr.length/2-1;i>=0;i--) {//从第一个非叶子结点从下至上,从右至左调整结构
    			adjustHeap(arr,i,arr.length);
    		}
    		
    		for(int j=arr.length-1;j>0;j--) {
    			swap(arr,0,j);//将堆顶元素与末尾元素进行交换
    			adjustHeap(arr,0,j);//重新对堆进行调整
    		}
    	}
    	public static void main(String[] args) {
    		int[] arr= {2,10,8,22,34,5,12,28,21,11};
    		System.out.println("堆排序前:");
    		System.out.println(Arrays.toString(arr));
    		heapsort(arr);
    		System.out.println("堆排序后:");
    		System.out.println(Arrays.toString(arr));
    	}
    }
    

    运行结果:

    堆排序前:
    [2, 10, 8, 22, 34, 5, 12, 28, 21, 11]
    堆排序后:
    [2, 5, 8, 10, 11, 12, 21, 22, 28, 34]
    

    2、小顶堆

    package Sort;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class HeapSort {
    	//调整小顶堆
    	/**
    	 * @param arr     待调整数组
    	 * @param i       非叶子结点在数组中的索引
    	 * @param length  调整元素个数(length在逐渐减少)
    	 */
    	public static void adjustHeap(int[] arr, int i, int length) {
    		int temp = arr[i];//取出当前元素i
    		for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始,即2i+1处开始
    			if (k + 1 < length && arr[k] > arr[k + 1]) {//如果左子结点大于右子结点,则k指向左子结点(arr[k]表示左子结点,arr[k+1]表示右子结点)
    				k++;
    			}
    			if (arr[k] < temp) {//如果子节点小于父节点,将子节点值赋给父节点(不用进行交换)
    				arr[i] = arr[k];
    				i = k;//i指向k,即将较大值放在较小值下方
    			} else {
    				break;//我们是自下而上进行调整即可保证下方子树已为小顶堆
    			}
    		}//当for循环结束后,我们将以i为父结点的树的最小值放在局部堆顶
    		arr[i] = temp;//将temp值放到调整后的位置
    	}
    	public static  void swap(int[] arr,int a,int b) {//交换元素
    		int temp=arr[a]; 
    		arr[a]=arr[b];
    		arr[b]=temp;
    	}
    	public static void heapsort(int[] arr) {
    		for(int i=arr.length/2-1;i>=0;i--) {//从第一个非叶子结点从下至上,从右至左调整结构
    			adjustHeap(arr,i,arr.length);
    		}
    		
    		for(int j=arr.length-1;j>0;j--) {
    			swap(arr,0,j);//将堆顶元素与末尾元素进行交换
    			adjustHeap(arr,0,j);//重新对堆进行调整
    		}
    	}
    	public static void main(String[] args) {
    		int[] arr= {2,10,8,22,34,5,12,28,21,11};
    		System.out.println("堆排序前:");
    		System.out.println(Arrays.toString(arr));
    		heapsort(arr);
    		System.out.println("堆排序后:");
    		System.out.println(Arrays.toString(arr));
    	}
    }
    

    运行结果:

    堆排序前:
    [2, 10, 8, 22, 34, 5, 12, 28, 21, 11]
    堆排序后:
    [34, 28, 22, 21, 12, 11, 10, 8, 5, 2]
    

    五、堆排序算法性能测试

    以大顶堆为例:

    package Sort;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class HeapSort {
    	//调整大顶堆
    	/**
    	 * @param arr     待调整数组
    	 * @param i       非叶子结点在数组中的索引
    	 * @param length  调整元素个数(length在逐渐减少)
    	 */
    	public static void adjustHeap(int[] arr, int i, int length) {
    		int temp = arr[i];//取出当前元素i
    		for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始,即2i+1处开始
    			if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点,则k指向右子结点(arr[k]表示左子结点,arr[k+1]表示右子结点)
    				k++;
    			}
    			if (arr[k] > temp) {//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
    				arr[i] = arr[k];
    				i = k;//i指向k,即将较小值放在较大值下方
    			} else {
    				break;//我们是自下而上进行调整即可保证下方子树已为大顶堆
    			}
    		}//当for循环结束后,我们将以i为父结点的树的最大值放在局部堆顶
    		arr[i] = temp;//将temp值放到调整后的位置
    	}
    	
    	public static  void swap(int[] arr,int a,int b) {//交换元素
    		int temp=arr[a]; 
    		arr[a]=arr[b];
    		arr[b]=temp;
    	}
    	
    	public static void heapsort(int[] arr) {
    		for(int i=arr.length/2-1;i>=0;i--) {//从第一个非叶子结点从下至上,从右至左调整结构
    			adjustHeap(arr,i,arr.length);
    		}
    		
    		for(int j=arr.length-1;j>0;j--) {
    			swap(arr,0,j);//将堆顶元素与末尾元素进行交换
    			adjustHeap(arr,0,j);//重新对堆进行调整
    		}
    	}
    	public static void main(String[] args) {
    		int[] arr = new int[8000000];
    		for (int i = 0; i < 8000000; i++) {
    			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
    		}
    
    		Date date1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");//SimpleDateFormat是Java提供的一个格式化和解析日期的工具类
    		String date1Str = simpleDateFormat.format(date1);
    		System.out.println("堆排序前的时间是:" + date1Str);
    		heapsort(arr);
    		Date date2 = new Date();
    		String date2Str = simpleDateFormat.format(date2);
    		System.out.println("堆排序后的时间是:" + date2Str);
    	}
    }
    
    
    堆排序前的时间是:2021-02-05 14:27:13
    堆排序后的时间是:2021-02-05 14:27:13
    

    堆排序测试800 0000个数据一共需要1s左右的时间。

    展开全文
  • 堆排序_排序_

    2021-09-30 15:11:49
    堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
  • 堆与堆排序

    千次阅读 2022-03-25 20:41:18
    堆排序 参考自:链接: link 1 概念 1) 堆的基本概念 堆 是一种特殊的树,满足以下条件即为堆: 首先堆是一个完全二叉树 堆中每一个节点的值都必须大于等于(或小于等于)其左右子节点的值 每个节点都大于等于其...

    堆排序

    参考自:链接: link

    1 概念

    1) 堆的基本概念
    堆 是一种特殊的树,满足以下条件即为堆:

    • 首先堆是一个完全二叉树
    • 堆中每一个节点的值都必须大于等于(或小于等于)其左右子节点的值
    • 每个节点都大于等于其子树节点的堆叫“大顶堆“或大根堆,根是最大值
    • 每个节点都小于等于其子树节点的堆叫“小顶堆“或小根堆,根是最小值

    因为堆的要求不像二叉搜索树那么严格。他只要求某个节点的子节点大于或小于该节点,因此同一组数据,可以构建多种不同形态的堆:
    在这里插入图片描述
    2)堆的表示
    堆是完全二叉树,大部分时候都是使用数组来存储堆
    在这里插入图片描述
    规律(根节点是0号)

    • i 结点的父结点 par = floor((i-1)/2) 「向下取整」

    • i 结点的左子结点 2 * i +1

    • i 结点的右子结点 2 * i + 2

    因为堆是完全二叉树,所以说,数组中的元素的父节点、孩子节点都是可以用公式算出来的!(层序遍历下)

    2 堆的操作

    堆的操作主要有两种:插入、删除。。(priority_queue也正是只提供了这两种方法)
    在这里插入图片描述

    不管是插入还是删除后都有可能不再满足堆的定义即:

    • 堆是一颗完全二叉树

    • 堆中每个节点都必须大于等于(或小于等于)其左右子节点

    在插入或删除操作后需要进行调整,让其重新满足堆的特性,这个调整的过程叫做堆化(heapify)

    1) 两种堆化方式

    从下往上(上浮):当前元素不断向上和父节点比较大小:

    • 大顶堆:当前元素比父节点大,交换,让大的节点上去
    • 小顶堆:当前元素比父节点小,交换,让小的节点上去

    在这里插入图片描述

    从上往下(下沉):当前元素不断向下和两个孩子节点比较大小

    • 大顶堆:当前元素与子节点中较大的比,比子节点小交换,让小的节点下去
    • 小顶堆:当前元素与子节点中较小的比,比子节点大交换,让大的节点下去

    在这里插入图片描述当根节点是0号的时候,下沉和上浮代码是:

    
    //模拟priority_queue
    class Heap
    {
    private:
        vector<int> vec;
        int capacity;
        int count;
    
    
        void swapNode(int i,int j)
        {
            swap(vec[i],vec[j]);
        }
    
        //小根堆的上浮操作---在堆中将index节点上浮
        void siftup_minheap(int index)
        {
            int parentNode=(index-1)/2;
            while(parentNode>=0)
            {
                if(vec[parentNode]<vec[index])
                    break;//父节点比这个节点小,则停止上滤
                
                swapNode(index,parentNode);
                index=parentNode;
                parentNode=(index-1)/2;
    
            }
        }
    
    
        //小根堆的下沉操作--下沉的范围是[index,n),一般是vec.size()
        void siftdown_minheap(int index,int n)
        {
            int i=index;
            int j=2*i+1;//index节点的左儿子
            while(j<n)
            {
                if(j+1<n && vec[j+1]<vec[j]) j++;//j是左儿子和右儿子。较小的那个的下标
                if(vec[i]<vec[j]) break;//如果 当前节点比两个孩子都要小,那么停止下沉
                swapNode(i,j);
                i=j;
                j=2*i+1;
            }
        }
    
    
    
    };
    

    2) 插入

    插入的过程是从下往上的堆化:在堆的尾部插入,以满足完全二叉树条件,再进行堆化。
    在这里插入图片描述

    过程:

    • 让新插入的节点与父节点对比大小。如果新插入的节点大于父节点,我们就互换两个节点。一直重复这个过程,直到满足堆的条件。

    在这里插入图片描述

    java代码如下:

     void del()
        {
            int n=vec.size();
            swapNode(0,n-1);
    
            vec.pop_back();
    
            siftdown_minheap(0,vec.size());
    
        }
    

    3) 删除堆顶元素

    堆的删除操作,往往是删除堆顶的元素
    删除非堆顶元素的效率不高,意义通常也不大。

    删除堆顶元素,过程是从上往下的堆化。

    堆顶元素存储的就是堆中数据的最大值或者最小值。删除了堆顶元素后,可以把最后一个元素移到根节点的位置,满足完全二叉树的条件,再进行堆化
    在这里插入图片描述

    最后一个节点放到堆顶,在子节点中找出较大(大顶堆)的那个对比。小于子节点时,互换两个节点,并且重复进行这个过程。这就是从上往下的堆化方法。
    在这里插入图片描述
    java代码如下:

    //删除顶部元素
    removeMax() {
      if (count == 0) return -1; // 堆中没有数据
      a[1] = a[count];//最后一个元素移到根节点的位置
      --count;
      sink(a, count, 1); 
    }
    // 自上往下堆化
    sink(a, n, i) { 
      while (true) {
        const maxPos = i;
        if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
        if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1; // 需要在两个子节点中找大的出来
        if (maxPos == i) break;
        swap(a, i, maxPos);
        i = maxPos;
      }
    }
    

    3) 堆化时间复杂度
    堆化的过程是顺着节点所在路径比较交换的,所以堆化的时间复杂度跟树的高度成正比,也就是 O(logn)。

    4)插入和删除时间复杂度

    插入数据和删除堆顶元素的主要逻辑就是堆化,所以时间复杂度都是 O(logn)。

    3 堆排序

    堆排序步骤

    • “大顶堆”用于升序排列

    • “小顶堆”用于降序排列

    实现堆排序可分解为两个步骤,建堆和排序

    1)建堆

    数组原地建成一个堆。所谓“原地”就是,不借助另一个数组,就在原数组上操作

    方式一(从前往后处理数组)

    从前往后依次处理数组元素,数据插入堆中时,都用从下往上堆化。直到最后一个元素处理完成。

    在这里插入图片描述
    假设,起初堆中只包含一个数据,就是index=1 的元素6

    • Step1:6这个元素,只有一个,不需要比较;
    • Step2:调用前面讲的插入操作,将index=2的元素8插入堆中。
      堆化:这里8大于堆顶6,堆化后8与6交换位置
    • Step3:将index=3的元素3插入堆中。
      堆化:这里3小于index 3/2=1的位置上的元素8,不需要交换;
    • Step4:将index=4的元素10插入堆中。
      堆化:这里10大于index 4/2=2上的元素6,交换,再与index=2/2=1上的8比,比8大,交换
    • Step5:……
    • Step6:将index从 2 到 n 的数据依次插入到堆中,完成建堆。

    除了第一个节点,都需要堆化。即对n-1个节点进行了堆化。时间复杂度是NlogN。(需要复杂的公式推导,记住就行了)

    这个过程,虽然是原地操作,往往,我们会有下面这种情况:
    给定一个数组,遍历这个数组,往一个priority_queue中插入元素。
    这个过程,本质上就是方式一的方法,也就是在原地在数组中从前往后调整,所以时间复杂度也是NlogN。(往prirotity——queue中插数据,本质上就是差插到pri_queue底部的那个数组的末尾,然后上浮。)

    方式二(从后往前处理数组)

    从后往前处理数组,使用从上往下堆化,直到第一个元素处理完成。

    对于完全二叉树来说,叶子节点:

    • 根节点是1开始编号的时候,下标从 n/2+1 到 n 的都是叶子节点。所以第一个非叶子节点为n/2
    • 根节点是0开始编号的时候,第一个非叶子节点是最后一个节点的父节点,也就是(n-1-1)/2=(n-2)/2

    在这里插入图片描述

    叶子节点往下堆化只能自己跟自己比较,所以从最后一个非叶子节点index=4开始堆化

    • Step1:index=4的元素8小于子节点16,交换位置
    • Step2:index=3的元素19小于子节点20,交换位置
    • Step3:index=2的元素5小于子节点16,交换位置,再次小于子节点13,交换位置
    • Step4:index=1的元素7小于子节点20,交换位置,再次小于子节点19,交换位置。完成建堆。

    下标从 n/2 开始到 1 的节点进行堆化。

    结论:

    • 对比方式一的n-1个节点堆化,采用从后往前处理数组的方式较好

    时间复杂度:因为叶子节点不需要堆化,所以需要堆化的节点从倒数第二层开始,每个节点堆化的过程中,需要比较和交换的节点个数是与它的高度k成正比的。
    在这里插入图片描述

    建堆的时间复杂度是 O(n)

    2)排序
    排序是建立在已经构建一个堆的基础上的。数组中的第一个元素就是堆顶,也就是最大或最小的元素。我们可以利用删除堆顶元素的思路来进行堆排序。
    在这里插入图片描述

    • Step1:将堆顶元素9与第n个元素(index=5)交换,此时最大值位于5(数组最后位),下标为5的元素位于堆顶
      堆化:5小于子节点中较大的6,与6交换位置

    • Step2: 再取此时的堆顶元素6 与n-1个元素(index=4)交换
      堆化:1小于子节点中较大的5,与5交换位置

    • Step3: 再取堆顶元素5 与n-2个元素(index=3)交换
      堆化:3大于子节点1,不交换

    • Step4: 再取堆顶元素3 与n-3个元素(index=2)交换

    • Step5: 再取堆顶元素1,发现没有可比较的子节点了,堆排序结束

    排序过程中需要对n个元素进行堆化,堆化的时间复杂度是O(logn),所以排序过程的时间复杂度是 O(nlogn)

    排序结果:

    • 大顶堆:升序数组
    • 小顶堆:降序数组

    堆排序复杂度
    时间复杂度:堆排序包括建堆和排序两个操作,建堆过程的时间复杂度是 O(n),排序过程的时间复杂度是 O(nlogn),所以,堆排序整体的时间复杂度是 O(nlogn)

    空间复杂度:排序不需要占用额外的空间,只需要交换元素的需要一个临时变量,所以堆排序的空间复杂度为O(1)。

    4堆应用

    1)优先级队列就是使用的堆封装的
    2)其他应用见参考:https://juejin.cn/post/7007610680891146271

    5 代码

    #include<vector>
    #include<iostream>
    using namespace std;
    
    //模拟priority_queue
    class Heap
    {
    public:
        vector<int> vec;
        int capacity;
        int count;
    
    
        void swapNode(int i,int j)
        {
            swap(vec[i],vec[j]);
        }
    
        //小根堆的上浮操作---在堆中将index节点上浮
        void siftup_minheap(int index)
        {
            if(index==0) return;
            cout<<"..."<<endl;
            int parentNode=(index-1)/2;
            while(parentNode>=0)
            {
                
                if(vec[parentNode]<vec[index])
                    break;//父节点比这个节点小,则停止上滤
                
                swapNode(index,parentNode);
                index=parentNode;
                if(index==0) break;
                parentNode=(index-1)/2;
    
            }
        }
    
    
        //小根堆的下沉操作--下沉的范围是[index,n),一般是vec.size()
        void siftdown_minheap(int index,int n)
        {
            int i=index;
            int j=2*i+1;//index节点的左儿子
            while(j<n)
            {
                if(j+1<n && vec[j+1]<vec[j]) j++;//j是左儿子和右儿子。较小的那个的下标
                if(vec[i]<vec[j]) break;//如果 当前节点比两个孩子都要小,那么停止下沉
                swapNode(i,j);
                i=j;
                j=2*i+1;
            }
        }
    
        //小根堆的插入操作
        void insert(int num)
        {
            vec.push_back(num);
            int index=vec.size();
            siftup_minheap(index-1);
        }
    
        //小根堆的删除堆顶元素操作--先将根节点和末尾元素互换,然后popback,然后从根节点开始下沉
        void del()
        {
            int n=vec.size();
            swapNode(0,n-1);
    
            vec.pop_back();
    
            siftdown_minheap(0,vec.size());
    
        }
    
        //原地建堆的操作--复杂度是NlogN
        void  buildHeap_1()
        {
            for(int i=0;i<vec.size();i++)
            {
                siftup_minheap(i);
            }
        }
    
    
    
        //时间复杂度是N的,建堆方法--从第一个非叶子节点,往前遍历,并进行下沉操作
        void buildHeap()
        {
            int n=vec.size();
            for(int i=(n-2)/2;i>=0;i--)
            {
                siftdown_minheap(i,vec.size());
            }
        }
    
    
        int top()
        {
            int temp=vec[0];
            return temp;
        }
    
    
    public:
    
        Heap(vector<int>& vec_)
        {
            vec=vec_;
        }
    
    };
    
    int main()
    {
        vector<int> vec{9,4,7,1,5,3};
        Heap heap_(vec);
        heap_.buildHeap();
    
        while(heap_.vec.size()>0)
        {
            cout<<heap_.top()<<endl;
            heap_.del();
        }
    
        return 0;
    
    }
    
    
    
    展开全文
  • 堆排序建立初始堆

    万次阅读 多人点赞 2020-01-08 19:35:34
    例1.有一组记录的排序码为 (3,5,4,7,1,2),则利用堆排序方法建立的初始堆为 _____________?

    例1.有一组记录的排序码为 ( 3 , 5 , 4 , 7 , 1 , 2 ) (3, 5, 4, 7, 1, 2) (3,5,4,7,1,2),则利用堆排序的方法建立的初始堆为 _____________?

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    所以初始堆为 ( 7 , 5 , 4 , 3 , 1 , 2 ) (7,5,4,3,1,2) (7,5,4,3,1,2)

    展开全文
  • 详解堆排序

    千次阅读 多人点赞 2020-07-10 07:56:25
    (1) 堆排序利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。 (2) 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其...
  • 堆排序算法详解

    万次阅读 多人点赞 2018-10-14 16:45:41
    一、堆排序算法原理和动态图解  将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新...
  • 在以往工作或者面试的时候常会碰到一个问题,如何实现海量TopN,就是在一个非常大的结果集里面快速找到最大的前10或前100个数,同时要保证内存和速度的效率,我们可能第一个想法就是利用排序,然后截取前10或前100,...
  • 堆排序算法C语言程序,亲测可用,堆排序算法是基于选择排序算法思想,利用堆结构和二叉树的一些性质来完成数据的排序。
  • C语言实现堆排序

    2022-04-14 13:38:59
    堆是一种特殊的二叉树数据结构,分为大根堆与小根堆,大根堆即二叉树即其子树都满足:根节点的值大于子树根节点的值。小根堆相反。堆排序就是利用堆的性质将数据排序。
  • 堆和堆排序:为什么说堆排序没有快速排序快

    千次阅读 多人点赞 2019-01-22 10:23:50
    堆这种数据结构的应用场景非常多,最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为O(nlogn)的排序算法。 前面我们学过快速排序,平均情况下,它的时间复杂度为O(logn)。尽管这两种排序算法的时间复杂度...
  • 堆排序(Heapsort)

    千次阅读 2021-01-15 22:26:30
    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。 堆是一个近似完全二叉树的结构,并同时满足堆积的性质: 即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序的平均时间复杂度为 Ο...
  • Java实现堆排序及详细图解

    千次阅读 2021-08-23 11:39:12
    堆排序(HeapSort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似于完全二叉树的结构,同时满足子节点的键值总是小于(或者大于)其父节点。 每个节点的值都大于或者等于其左右子节点的值,称为大...
  • 十大经典排序算法-堆排序算法详解

    千次阅读 多人点赞 2020-07-01 17:01:46
    堆排序(Heapsort)是利用二叉堆的概念来排序的选择排序算法,分为两种: 升序排序:利用最大堆进行排序 降序排序:利用最小堆进行排序 2.算法原理 给定一个最大堆如下图所示,以该最大堆进行演示堆排序 首先,...
  • 堆排序(C语言)

    千次阅读 多人点赞 2020-06-27 17:00:18
    堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
  • 堆排序是什么?

    千次阅读 2021-02-23 20:56:34
    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序可以说是一种利用堆的...
  • 堆排序算法之初始堆建立

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

    千次阅读 2019-04-02 10:56:54
    堆排序与TopK的问题,面试中还是经常问的,索性也整理一下。下面是徒手写的,供参考. 堆排序 public void heapSort(int[] array) { // 先构造一个大顶堆 int N = array.length - 1; for (int i = (N - 1) / 2; i ...
  • 堆排序堆排序详解

    千次阅读 2021-09-10 13:46:59
    堆排序利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。 堆 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子...
  • 利用堆实现堆排序&优先队列

    千次阅读 2014-06-19 12:15:39
    此处设计到三个大顶堆的操作:(1)自顶向下调整操作:MaxHeapify(对应的SiftDown操作)、(2)利用数组建立大顶堆:BuildMaxHeap、(3)不断交换顶元素(的最大元素)和的末尾元素,实现非递减排序。...
  • 堆排序(超详细图解 java版)

    千次阅读 多人点赞 2022-04-08 21:25:42
    l) 堆排序利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为0(nlogn),它也是不稳定排序。 2)堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右...
  • 堆排序算法(图解详细流程)

    千次阅读 2021-11-14 10:44:54
    堆排序利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏最好,平均时间复杂度均为O(nlogn),他也是不稳定排序 堆是具有以下性质的完全二叉树,每个节点的值都大于或等于其左右孩子节点...
  • 排序算法——堆排序

    千次阅读 2019-07-22 14:48:18
    在介绍堆排序之前我们首先应该弄清楚堆排序可以解决什么问题,答案是显而易见的:排序。说得通俗点儿就是对一组无序的数字进行调整,使其按照从大到小或者...堆排序(Heapsort)是指利用堆这种数据结构所设计的一种...
  • 堆排序(C语言简单实现)

    千次阅读 2020-11-30 17:44:11
    堆排序(Heap Sort)就是利用堆进行排序的方法 。基本思想:将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),...
  • 四、堆排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 五、冒泡排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 六、快速排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 七..

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 142,032
精华内容 56,812
关键字:

则利用堆排序的方法