堆的基本概念堆排序是一种非常重要的排序算法，是一种高效的排序算法，复杂度为O(nlogn)，堆排序不仅是面试的重点，在很多实际算法中也会用到，比如经典的TopK算法和用来实现优先级队列的小顶堆。堆排序是利用堆的数据结构设计的一种排序算法。堆实际上是一个完整的二叉树结构。问：那么什么是完全二叉树？答：假设一棵二叉树的深度为h，除第h层外，其他层（1～h-1）的节点数已达到最大数，第h层的所有节点不断集中在最左边。是一棵完全二叉树。我们知道堆是一棵完全二叉树，所以堆分为两种堆：大顶堆和小顶堆。它们满足一个重要的性质：小顶堆满足：Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]大顶堆满足：Key[i]>=Key[2i+1]&&key>=key[2i+2]怎么理解呢，其实很简单，顾名思义，bigtop堆的最大元素在根节点。堆的性质决定了大顶堆中的节点必须大于等于它的子节点。相反，小顶堆的最小元素在根节点。先来看看大顶堆和小顶堆的示意图：堆排序的基本思路和步骤。把顶元素和末元素交换，除去末元素，可以形成一个新的大顶堆。由于第二个堆顶元素与最后一个元素交换，新创建的堆不是大顶堆，需要重建大顶堆。重复上述过程，直到堆中只剩下一个元素。假设我们有一个数组arr=[4,6,7,2,9,8,3,5]需要排序，我们将这个数组构造成二叉树，如下图：问：此时我们需要把这个完全二叉树构造成一个大顶堆，怎么构造呢？答：一个好的方法是遍历二叉树的非叶子节点，从下到上构造一个大的顶堆。对于每一个非叶子节点，将其与其左右子节点进行比较，将最大值更改为子树的父节点。Q：为什么从非叶子节点开始而不是最后一个节点？答：因为叶子节点下没有子节点，所以不需要操作。Q：为什么要从下往上遍历非叶子节点，而不是从上往下遍历？答：我们从底部开始遍历，调整每个节点使其成为其左右节点的最大值。如果一直往上走，根节点一定是最大值；如果不满意，调整之后，top可能又不满意了，所以最好的解决办法是从下到上。那么我们构造大顶堆的代码就很明显了：#构造一个大顶堆，从非叶子节点开始倒序遍历，所以l//2-1就是最后一个非叶子节点l=len(arr)foriinrange(l//2-1,-1,-1):build_heap()#遍历为每个非叶子节点构造一个大的顶堆。看我们的例子，非叶子节点有2,8,6,4，我们从最后一个非叶子节点，也就是5开始遍历，构造一个大顶堆。2和5比较，5比较大，所以从数组中交换arr[3]和arr[7]，然后完成第一个非叶子节点的替换。以下节点继续交换。此时9和4交换后，4节点下的树不符合大顶堆，所以要再次将节点4与其左右节点进行比较，换成更大的值，4后比较左右子节点，应该和6交换位置。至此，整个二叉树就是一个完整的大顶堆，每个节点都不小于左右子节点。这时候我们交换堆的根节点的位置，即数组9的最大值和数组的最后一个元素2，然后9排序后放在数组的最后一个位置。2到达根节点后，新堆不满足大顶堆，我们需要重复上面的步骤重构大顶堆，然后将大顶堆的根节点放在二叉树后面作为排序大批。这样就用大顶堆把数字一个一个排序。需要注意的一点是，我们上面9和2交换位置后，2在二叉树的根节点，2需要和右子树8交换位置，交换位置后，右子树需要递归调整大顶堆，但是左子树6已经满足大顶堆的性质，因为不需要再进行操作。我们来看一个直观的堆排序动画：代码实现：classSolution(object):defheap_sort(self,nums):i,l=0,len(nums)self.nums=nums#构造一个bigtopHeap,从非叶子节点逆序遍历，所以l//2-1是i在range(l//2-1,-1,-1)中的最后一个非叶子节点：self.build_heap(i,l-1)#以上循环完成了大顶堆的构建，然后开始交换根节点和尾节点，然后重新调整大顶堆forjinrange(l-1,-1,-1):nums[0],nums[j]=nums[j],nums[0]self.build_heap(0,j-1)returnnumsdefbuild_heap(self,i,l):"""建立大顶heap"""nums=self.numsleft,right=2*i+1,2*i+2##左右子节点下标large_index=iifleft<=landnums[i]
