# 堆排序 堆排序， 和TOP K 同时使用了最大堆和最小堆问题 参考： {% embed url="https://www.cnblogs.com/chengxiao/p/6129630.html" %} 堆 分为最大堆， 和最小堆， ## 最大堆 每个节点的值都大于或者等于他的左右孩子的值 ## 最小堆 每个节点的值都小于等于其左右孩子的值 ## 公式 左右孩子的计算方式： left := 2\*i + 1 right := 2 \* i +2 i 为下标索引 ## 堆排序的基本思想 首先需要将待排序序列构造成一个大顶堆， 假设待排序序列为array， 它的区间为【0，n】\(假设n代表的是下标\),需要将array\[0,n\] 构造成一个大顶堆，改造成大顶堆后，这个序列的头结点就是这个序列的最大值， 因此我们需要将头结点和尾节点的值互换，此时末尾的值就成为了最大值，之后我们在需要对序列array【0，n-1】重新构造成一个最大堆，然后将这个序列的头结点和序列的尾节点array\[n-1\] 互换，依次类推 ## 构建最大堆 这时候问题来了，我们如何构建一个最大堆，首先我们要找到倒数第一个非叶子节点，根据堆的特点  例如上图的大顶堆，我们从倒数第一个非叶子节点为 （n+1）/2 -1, 即下标为3，值为20 的节点开始，对他的左右节点进行置换，使得最大的数据放在下标为3这个节点上，这样下标为3的节点往下的树就是一个最大堆，之后我们开始倒序处理（**处理的顺序是从下往上，从左到右**）下标为2 的节点，处理完后，以下标为2 的节点往下的树成为一个最大堆，之后我们需要处理下标为1 的节点，这时候比较困扰的地方来了，我们需要处理下标为1，3， 4 的数据，似的最大的树要放到下标为1上，假设最终是下标1 和下标3 的数据进行了交换，这样我们就会打乱下标为3往下的最大堆关系，因此我们需要往下把下标为3的树重新交换，依次往下类推，最终的结果就是一个最大堆。 ## 堆排序 这样当我们对闭区间【0，n】构建成最大堆后，最大的数一定会存在根节点，即array【0】，因此我们需要将array【0】 和array【n】互换，这样最大的数就存在了这个区间的最后一个位置。 接下来，我们开始对闭区间【0，n-1】，重新构建最大堆，构建完后，收尾置换，这样第二个最大的数也找到了，之后我们不断的缩小区间【】，直到这个区间为只有一个数为止，这样就形成了堆排序 源码 ```go /* 区间是 [i,n] 闭区间，对array [i,n] 闭区间的数据进行最大堆操作操作， (1） i 的左节点是2*i+1 右节点是2*i+ 2 ，对 下标 是 i, 2*i +1 和2*i+2 的数据进行比较，这里要判断左节点和右节点是否超出界限，如果超出，break (2) 如果左节点是最大节点，则节点和左节点交换，同时要处理左节点下面的二叉树，走（1） (3) 如果右节点是最大节点，则节点和右节点交换，同时要处理右节点下面的二叉树，走（1） */ func down(array []int, i, n int) { index := i for { l := 2*index + 1 if l > n || l < 0 { break } r := 2*index + 2 // 注意j 要首先使用left 下标的值，认为此时l 肯定没有越界 j := l if r <= n && array[l] < array[r] { j = r } if array[index] >= array[j] {break} array[index],array[j]= array[j], array[index] index = j } } func HeapMaxSort(array []int) { for n := len(array)-1; n >=0; n -- { for i := (n+1)/2 - 1;i>=0; i--{ down(array,i, n) } array[0], array[n] = array[n], array[0] } } ``` ## 堆排序进阶 我们可以参照golang 源码，看看堆的实现， ## TOP K 的问题 top k 的问题 就是构建最大堆，最小堆的过程，并不是堆排序的过程，堆排序最终是构建完最大堆后，收尾置换，然后缩小区间，重复上述过程，top k的问题是构建堆后，对新来的数据 与堆头比较，符合条件后，讲新来的数据和堆头替换，重新构建堆 找出大量的数据，最小的前n 个数，我们需要用最大堆 找出大量的数据中最大的前n个数，我们需要用最小堆 ## 案例，找出大量数据中，最小的前k个数