三刷”数组中的第K个最大元素“，我终于学会了堆排序

2023-06-15 47

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 三刷”数组中的第K个最大元素“，我终于学会了堆排序

灵魂拷问

身为前端的你，数据结构排序算法掌握得怎么样了，我想大家对冒泡排序，插入排序，快速排序已经掌握了，业务代码中 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]
};