利用大顶堆进行堆排序找出数组的第K个最大元素-LeetCode模拟问题
最编程
2024-08-14 20:40:17
...
// 通过大顶堆求解问题
var findKthLargest = function(nums, k) {
// 堆的大小
let heapSize = nums.length;
// 调用大顶堆函数
buildMaxHeap(nums,heapSize);
// 要想求第K大的元素，就需要将大顶堆下沉K-1次，每下沉一次进行一次重新的堆化；
for (let i = 0; i < k - 1; i++ ) {
swap(nums,0,nums.length - 1 - i);
// 将最后一个元素忽略，不参与堆化
nums
heapSize--;
// 从第0个元素开始继续进行堆化
maxHeapify(nums,0,heapSize);
}
// 此时堆顶就是第K个最大元素
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) {
// 首先假定第i个是最大的
let max = i;
let leftChild = 2 * i + 1;
let rightChild = 2 * i + 2;
// 如果下标不越界（即子孩子存在），并且子节点小于第i个元素
if (leftChild < heapSize && nums[leftChild] > nums[max]) {
max = leftChild;
}
if (rightChild < heapSize && nums[rightChild] > nums[max]) {
max = rightChild;
}
// 判断是否发生了交换
if (max !== i) {
swap(nums,i,max);
// 交换之后，从下面上来的元素的位置后面需要继续进行堆化
maxHeapify(nums,max,heapSize);
}
}
function swap (nums,i,j) {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
};
findKthLargest([8,5,0,3,7,1,2], 3)
复制代码
下一篇： Python数据结构：理解大顶堆和小顶堆