❝堆排序整个流程可以总结为:
上浮下沉
❞
❝很多同学可能会想到这样一种解决,我把数组全部排序好,这样就可以拿到第k大的元素,这样是一种解法,但是我们是需要第K大的元素,
不一定要全部排序好再去拿,只针对部分元素进行排序
,这样的复杂度显然可以降低的 ❞
也就是可以转化为:「使用堆排序来解决这个问题——建立一个大顶堆,做k−1 次删除操作后,堆顶元素就是我们要找的答案」(堆排序过程中,不全部下沉,下沉
nums.length-k+1,然后堆顶可以拿到我们top k答案了)
堆排序是利用 「堆」 这种 「数据结构」 而设计的一种排序算法,它是一种选择排序,最坏 、最好、平均时间复杂度均为 O(nlogn)
,它是不稳定排序。
❝注意因为完全二叉树的性质,可以用数组表示对应的树结构(所以,堆排序过程中,你是看不到树这数据结构的,用数组进行映射了),这叫
顺序存储
❞
堆是具有以下性质的完全二叉树:
举例说明:
对堆中的节点按层进行编号,映射到数组中如下图
大顶堆特点:arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]
,i 对应第几个节点,i 从 0 开始编号
小顶堆特点:arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]
,i 对应第几个节点,i 从 0 开始
n-1
个元素重新构造成一个堆,这样 就会得到 n 个元素的次小值。如此反复,便能的得到一个有序序列。对数组 4,6,8,5,9
进行堆排序,将数组升序排序。
将给定无序序列构造成一个大顶堆。
叶节点不用调整,第一个非叶子节点 arr.length/2-1 = 5/2-1 = 1
,也就是 元素为 6 的节点。
比较时:先让 5 与 9 比较,得到最大的那个,再和 6 比较,发现 9 大于 6,则调整他们的位置。
[4,9,8]
中,9 元素最大,则 4 和 9 进行交换[4,5,6]
结构混乱,将其继续调整。[4,5,6]
中 6 最大,将 4 与 6 进行调整。此时,就将一个无序序列构造成了一个大顶堆。
将堆顶元素与末尾元素进行交换,「使其末尾元素最大」。然后继续调整,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。
这里想说的几点注意事项(代码实现的关键思路):
下沉操作
让尾部元素与堆顶元素交换,「最大值被放在数组末尾」,并且缩小数组的length,不参与后面大顶堆的调整调整
:「是从上到下,从左到右」,因为堆顶元素下沉到末尾了,要重新调整这颗大顶堆❝官方的代码模板我参考了下,比一些书籍写的都好记,所以可以参考作为堆排序的模板 ❞
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
// 整个流程就是上浮下沉
var findKthLargest = function(nums, k) {
let heapSize=nums.length
buildMaxHeap(nums,heapSize) // 构建好了一个大顶堆
// 进行下沉 大顶堆是最大元素下沉到末尾
for(let i=nums.length-1;i>=nums.length-k+1;i--){
swap(nums,0,i)
--heapSize // 下沉后的元素不参与到大顶堆的调整
// 重新调整大顶堆
maxHeapify(nums, 0, heapSize);
}
return nums[0]
// 自下而上构建一颗大顶堆
function buildMaxHeap(nums,heapSize){
for(let i=Math.floor(heapSize/2)-1;i>=0;i--){
maxHeapify(nums,i,heapSize)
}
}
// 从左向右,自上而下的调整节点
function maxHeapify(nums,i,heapSize){
let l=i*2+1
let r=i*2+2
let largest=i
if(l < heapSize && nums[l] > nums[largest]){
largest=l
}
if(r < heapSize && nums[r] > nums[largest]){
largest=r
}
if(largest!==i){
swap(nums,i,largest) // 进行节点调整
// 继续调整下面的非叶子节点
maxHeapify(nums,largest,heapSize)
}
}
function swap(a, i, j){
let temp = a[i];
a[i] = a[j];
a[j] = temp;
}
};
findKthLargest(nums,nums.length)
// 或者调整一下 let i=nums.length-1;i>=nums.length-k+1;的条件就行