灵魂拷问
身为前端的你，数据结构排序算法掌握得怎么样了，我想大家对冒泡排序，插入排序，快速排序已经掌握了，业务代码中 sort() 方法也用的不亦乐乎，但是提起堆排序肯定是马马虎虎，因为我也是，leetcode有这么一道题，我刷了3遍，终于弄明白了堆排序，今天和大家分享一下，如果能帮到你，那真是太好了！
题目
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5 示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
第一次刷
不就是个简单的数组排序嘛，从小到大排序之后，取倒数第k个元素不就完了
var findKthLargest = function(nums, k) { nums.sort(function(a,b) {return a-b}); return nums[nums.length-k]; };
js一行代码搞定，简单清晰，一看就懂。
但是看到评论区热评，让人顿觉羞愧，如果面试的时候，还在这里调API，这不是刷滑头嘛
第二次刷
既然不用sort()方法，那我自己写个快速排序吧，插入排序，冒泡泡序，面试官自己看吧，喜欢哪个我我给你写哪个。
function qsort(nums) { if (nums.length <= 1) { return nums; } const pivotIndex = Math.floor(nums.length / 2); const b = nums.splice(pivotIndex, 1)[0]; const left = [], right =[]; nums.forEach(item => { if (item > b) { left.push(item); } else { right.push(item); } }); return qsort(left).concat(b,qsort(right)); } var findKthLargest = function(nums, k) { return qsort(nums)[k-1]; };
自信满满得写出来了，一般小厂算法面试基本拿下，面试官还会觉得你基础扎实，如果能说出来，时间复杂度是Θ(n\lgn)，最坏情况是Θ(n2)，那基本稳了。
但是直到，参加高德地图的面试，
- 上来就是问的原题，返回数组中第K个最大元素，使用堆排序。
- 我一时语塞，半天没说话，这不按套路出牌啊
- 面试官，继续发问，有听说堆排序吗
- 我说听说，但没有写过
- 面试官：好吧，那就不问了
- ......结果当然是凉凉了
于是痛定思痛，决心一定要搞清楚堆排序
第三次刷
看到了leetcode的题解，大大得写着一句话
所以今天带着大家一起用堆排序重刷一遍
前置知识
- 堆 heap
- 完全二叉树
- 父节点内容大于子节点内容 堆必须满足 以上两个条件，必须是完全二叉树，且父节点大于子节点
- 完全二叉树 以下图中的树，都是完全二叉树
完全二叉树的特点就是，生成的时候，从上往下，从左到右，依次添加，下面的7个图，可以看成是生成完成二叉树的过程。
- 父节点内容大于子节点内容
故名思义，每个父节点的内容，都大于它的子节点的值，就不展开解释了
怎样用代码表示一个堆
用数组可以表示一个堆 因为堆是从上至下，从左至右构建的，我们可以给每个节点加上标识
正好可以用一个数组来存储这些标识 数组的下标对应堆的顺序标识，数组每一项的值，表示堆的节点的值
var arr = [10，5，8，3，4，6，7，1，2]
从任一节点出发，都可以拿到这个节点的父节点，和子节点
如第4个节点，i= 3
那么他的父节点的在数组中的顺序为：parent = Math.floor((i-1)/2) = 1
他的子节点的在数组中顺序为：
c1 = 2i+1 = 7
c2 = 2i+2 = 8
如第4个节点是 arr[3] = 3 他的父节点 是arr[1] = 5 他的两个子节点是arr[7] = 1 arr[8] = 2
用数组方便我们找到他的父节点和子节点
完全二叉树转化为堆的过程
我们把完全二叉树转化为堆的过程称为heapify，需要从上到下，对每个节点进行heapify操作，保证这个完全二叉树的每个父节点都大于子节点
接下来我们着手实现一下代码heapify的过程
入参数 arr 表示数组，n表示这数组的长度，也是树的节点个数，i表示对哪个节点进行heapify操作
c1 c2 分别为节点i的两个子节点，我们需要在i c1 c2 三个节点中找到最大值
当最大值为i 时，不需要交换
当最大值为c1 或者 c2，需要交换
交换之后，继续对下一个节点做 heapify 操作
直到每个节点都做完heapify 操作之后，跳出递归
测试代码为 [10, 5, 3, 4, 1, 2]
function swap(arr,i,j){ let temp = arr[i] arr[i] = arr[j] arr[i] = temp } function heapify(arr,n,i){ if(i>=n){ return } let c1 = 2 * i + 1 let c2 = 2 * i + 2 let max = i if(c1<n && arr[c1]>arr[max]){ max = c1 } if(c2<n && arr[c2]>arr[max]){ max = c2 } if(max !== i){ swap(arr,max,i) heapify(arr,n,max) } } funtion test(){ let arr = [4,10,3,5,1,2] let n = arr.length heapify(arr,n,0) console.log(arr) }
处理一个乱序的树
如果给定我们一个乱序的树，我们如何处理
只要对这个树所有非叶子节点，从下至上进行heapify 即可
比如上面这个节点，最后一个非叶子节点3，从下至上依次heapify是 3 -> 2 -> 1 -> 0
那么问题来了，如何找到最后一个非叶子节点3呢，最后一个非叶子节点，也就是树的最后一个节点的父节点
对应到图中就是 最后一个节点 8 的父节点 3
我们可以利用公式计算 parent = Math.floor((8-1)/2) = 3
代码处理
入参数 arr 表示数组，n表示这数组的长度，也是树的节点个数
对parnt 以上的所有节点进行heapify操作
function build_heap(arr,n){ let last_node = n-1 let parent = Math.floor((last_node -1)/2) for(let i = parent;i>=0;i--){ heapify(tree,n,i) } }
如何排序
当我们经过上面两个操作之后，拿到一个堆结构，那么如何排序呢
我们能确定的是，这个堆的根个节点肯定最大值
只要依次输出根节点，然后堆进行heapify操作，始终保持根节点是剩余值的最大值，就可以拿到一个降序的结果
如何输出根节点呢，将根节点和最后一个节点做交换，然后再砍断最后一个节点。
这样做的目的是为了保持结构始终一个完全二叉树，便于我们之后的heapify的操作
代码实现
function heap_sort(arr,n){ build_heap(arr,n) for(let i= n-1;i>0;i--){ swap(arr,i,0) heapify(arr,i,0) } }
总结
总的过程包括 建堆 build_heap 调整 heapify 排序 heap_sort
堆排序找出最大的k值： 时间复杂度：O(k * logn) 空间复杂度：O(1)，在原数组进行修改
完整代码如下
/** * @param {number[]} nums * @param {number} k * @return {number} */ function swap(nums,i,j){ let temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } function heapify(tree,n,i){ if(i>=n){ return } let c1 =2*i+1 let c2 = 2*i +2 let max = i if(c1<n && tree[c1]>tree[max]){ max = c1 } if(c2<n && tree[c2]>tree[max]){ max = c2 } if(max !==i){ swap(tree,max,i) heapify(tree,n,max) } } function heap_build(tree,n) { let last_node = n-1 let parent = Math.floor((last_node-1)/2) for(let i = parent;i>=0;i--){ heapify(tree, n, i); } } function heap_sort(tree,n){ heap_build(tree,n) for(let i = n-1;i>=0;i--){ swap(tree,i,0) heapify(tree,i,0) } } var findKthLargest = function(nums, k) { heap_sort(nums,nums.length) return nums.reverse()[k-1] };
