【算法】堆排序
2021-06-19 23:06
标签：alt str 搜索 结构 坐标 建立 uil 参数 i+1 1、什么是堆 （1） 堆是具有以下性质的完全二叉树（那么，什么是完全二叉树呢？完全二叉树是一种除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐的树）：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图： 同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子 该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是： 大顶堆：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] 小顶堆：arr[i] 比如20 10 15 这三个数的关系，i表示坐标，i=3时，对应的arr值为20，i=3*2+1=7，arr值为10，i=3*2+2=8，arr值为15，所以2*i+1和2*i+2是这么来的。 （2） 堆的起始坐标从1开始算： 比如说当前节点在list中的坐标为i 那么他的左节点坐标：2i 那么他的右节点坐标：2i + 1 找到它的父节点：i//2 （3） 堆的坐标从0开始算： 比如说当前节点在list中的坐标为i 那么他的左节点坐标：2i+1 那么他的右节点坐标：2i + 2 找到它的父节点：(i-1)//2 （4） 堆也叫做优先队列 （5） 上滤：新插入元素和父节点比对，发生交换，当发生了新插入结点和父结点没有交换的情况，那么上滤过程结束 （6） 下滤：左右节点比对后发生交换，将大的元素上调，不断重复，直到不需要调整或者调整到堆底，如下图 2、什么是二叉树及二叉树的一些概念 （1） 结点的度：结点拥有的子树的数目 （2） 叶子：没有子节点，度为零 （3） 森林：多个不相交的树，多个树 （4） 满二叉树：每个结点下都挂了2个子节点 （5） 完全二叉树：叶子结点只能出现在最下层和次下层，最下层的叶子结点集中在树的左部。满二叉树一定是完全二叉树，一个完全二叉树不一定是满二叉树。 （6） 二叉搜索树（又叫二叉查找树）：左边的结点都小于根结点，右边的结点都大于根结点 3、堆排序介绍 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(n*logn)，它也是不稳定排序。 4、堆排序的核心算法 （1） 建堆：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点 （2） 把堆顶的元素和最下最右一个元素交换，此时，最大的元素就排到了最后面 （3） 对于新的root节点，继续建堆，这样会得到n个元素的次小值 （4） 重复上面的1到3步，便能得到一个有序序列了 5、堆排序基本思想及步骤 步骤一 构造初始堆（从堆最下层开始构造，并且需要进行上虑操作）。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。 假设给定无序序列结构如下： 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，最后一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从后往前，从下往上的第一个非叶子节点进行调整。 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。 此时，我们就将一个无需序列构造成了一个大顶堆。 步骤二 将堆顶元素与末尾元素进行交换，也就是与堆的最下最右的元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。 将堆顶元素9和末尾元素4进行交换 重新调整结构，使其继续满足堆定义 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序 总结：对于堆排序的核心算法就是堆结点的调整 6、堆排序代码 # encoding=utf-8 #左叶子、右叶子和父节点，三个元素，找到最大的一个 def maxHeap(heap,heapSize,i): #i为某个节点 #它的左节点坐标：2i #那么它的右节点坐标：2i + 1 #它的父节点：i/2 left = 2*i +1 right = 2*i +2 larger = i #通过2次if的比较，将left、right和lager三者的最大值找到，这里假设当前是一个已经构建好的堆 if left
larger = left if right
larger = right #如果lager的值不是i，说明i的值需要和最大值进行交换 #因为i的坐标是最大堆的堆顶，所以必须是最大值 if larger != i: heap[i],heap[larger] = heap[larger],heap[i] maxHeap(heap,heapSize,larger) #以上步骤完成，堆顶坐标为i坐标的最大子堆建立好了 def buildMaxHeap(heap): #heap参数是未排序，未建堆的list heapSize = len(heap) #堆的长度//2可以找到堆里面的 #最后一个带有子节点的节点 #循环可以实现从堆的最下层节点开始建堆 #每次建立的堆都是一个最大堆 #简单来说把所有字段都建成最大堆 #然后组成了最终的最大堆 # (heapSize-1)//2当坐标从0开始算时，算出了当前堆中最后一个含有子节点的结点坐标 #这个循环要理解一下：这个循环调用，表示从最下层的子树，开始实现最大堆，这个就是我刚才说的从最下层开始建立最大堆的过程 for i in range((heapSize-1)//2,-1,-1): maxHeap(heap,heapSize,i) def heapSort(heap): #先把所有元素先建立一个最大堆 buildMaxHeap(heap) #将堆中所有的元素都遍历一遍 #让每个元素都做一次堆顶 #然后将堆顶的每个元素都换到堆的最后一个节点 for i in range(len(heap)-1,-1,-1): heap[0],heap[i] = heap[i],heap[0] #maxheap中的i是列表的长度，这样可以防止追加到 #堆后面的元素重新被当做最大堆元素进行建队 maxHeap(heap,i,0) return heap #第一次循环时，把最大值放到了列表最后面 #把最后一个值（肯定不是最大值）放到了堆顶 #把不包含最后一个元素的剩余元素，重新进行最大堆 #第二次循环的时候，把堆顶（次大值）放到了列表倒数的第二位置 #然后把不包含最后2个元素的剩余元素，重新进行建立最大堆 ……… #循环结束，那么列表的数据就排好了 if __name__ == ‘__main__‘: heap1 = [3,4,5,6,23,4,1,1,23,45,6678] print (heap1) heapSort(heap1) print (heap1) 7、堆排序的时间复杂度 堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(N*logN)级。 【算法】堆排序 标签：alt str 搜索 结构 坐标 建立 uil 参数 i+1 原文地址：https://www.cnblogs.com/jingsheng99/p/9689818.html
