脚本宝典收集整理的这篇文章主要介绍了堆排序以及TopK大顶堆小顶堆求解方式（js版），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
堆排序是一种选择排序，@R_629_1304@o(nLOGn),空间复杂度o(1)。数据结构底层是数组，通过索引之间的关系可看二叉树，父结点总是大于或者小于孩子结点。这就是堆的结构。刚初始完的堆是占据整个数组的。开始排序后，数组分为两个部分！前面是堆，后面是已排序完的有序子数组。排序时，堆顶元素和堆尾元素会交换，有序子数组长度+1，堆长度-1；此时，原堆尾元素占据了堆顶，可能会破坏了堆结构，所以，需要堆化，也就是堆顶元素要保持最大或者最小。当堆只有一个元素，自动加入有序子数组；这时有序子数组占据整个数组。排序完成。
将普通数组初始为堆。
把数组arr看成一个二叉树，父结点与孩子结点的关系：root:i , leftChild:2i+1, rightChild:2i+2找到索引最大的非叶子节点。数组长度length，假设length- 1= 2i + 1，则i=length/2 - 1。所以索引最大的非叶子结点是arr[i]。堆化。也就是将[i,length - 1]的数组变成堆，然后i - 1,使堆长度+1，再堆化，这样反复操作，直到i == 0，让堆占满整个数组。
//@H_126_13@初始堆
for (let i = (arr.length >> 1) - 1; i >= 0; i--) {
//堆化
}
//compare=(a,b)=>a>b :最大堆；compare=(a,b)=>a<b :最小堆 /** * i 堆顶索引 * end 堆尾索引+1 * compare 控制是最大堆还是最小堆 */ function adjustHeap(arr, i, end, compare) { let tmp = arr[i]; let parentIndex = i; let childIndex = 2 * i + 1; while (childIndex < end) { if (childIndex + 1 < end && !compare(arr[childIndex], arr[childIndex + 1])) { childIndex++; } if (!compare(tmp, arr[childIndex])) { arr[parentIndex] = arr[childIndex]; parentIndex = childIndex; childIndex = (childIndex << 1) + 1; } else { break; } } arr[parentIndex] = tmp; }
1.一开始，堆占据整个数组。取出堆顶元素，与堆尾元素交换。交换后，堆尾加入有序子数组，堆长度-1。2.所有堆元素加入有序数组后，排序完毕。3.小顶堆用于降序排序，大顶堆用于升序排序。
for (let j = arr.end- 1; j > 0; j--) { [arr[0], arr[j]] = [arr[j], arr[0]];//交换堆顶堆尾 adjustHeap(arr, 0, j, compare);//堆尾索引-1，并且堆化 }
function sort(arr, compareFunction) { function defaultCompare(a, b) {//默认大顶堆，也就是升序排序 return a > b; } let compare = compareFunction || defaultCompare; for (let i = (arr.length >> 1) - 1; i >= 0; i--) {//从后往前数，第一个非叶子结点开始初始化堆 adjustHeap(arr, i, arr.length, compare);//堆正在变长 } for (let j = arr.length - 1; j > 0; j--) { [arr[0], arr[j]] = [arr[j], arr[0]];//有序子数组正在变长 adjustHeap(arr, 0, j, compare);//堆正在缩小 } //排序完成 } //堆化 //compare=(a,b)=>a>b :大顶堆；compare=(a,b)=>a<b :小顶堆 /** * i 堆顶索引 * end 堆尾索引+1 * compare 控制是最大堆还是最小堆 */ function adjustHeap(arr, i, end, compare) { let tmp = arr[i]; let parentIndex = i; let childIndex = 2 * i + 1; while (childIndex < end) { if (childIndex + 1 < end && !compare(arr[childIndex], arr[childIndex + 1])) {//找到孩子结点更大(小)的一个 childIndex++; } if (!compare(tmp, arr[childIndex])) {//父结点不如孩子结点大（x小）的话，交换 arr[parentIndex] = arr[childIndex]; parentIndex = childIndex; childIndex = (childIndex << 1) + 1; } else { break; } } arr[parentIndex] = tmp; }
拿小顶堆举例来说，堆顶就是当前K个中最小的。如果最大的前K个元素都在这个堆中，那堆顶就是第K大的那个元素。
初始化堆，堆的大小为k。（直接拿数组前K个元素初始就行）从arr[k]（第k+1个元素）开始和堆顶作比较，如果大于堆顶就和堆顶交换；交换后，堆顶可能不是堆中最小元素，所以需要堆化。不断地有更大的元素被换入堆中，并且堆顶又能保持堆中最小。当arr[length-1]也比较完成后，堆中就包含了最大的K个元素了，并且堆顶arr[0]就是第K大的元素。时间复杂度o(nlogk)
function findTopK(arr, k, compareFunction) { function defaultCompare(a, b) { return a > b; } let compare = compareFunction || defaultCompare; for (let i = (k >> 1) - 1; i >= 0; i--) {//将[0,k-1]区间作为堆 adjustHeap(arr, i, k, compare); } for (let j = k + 1; j < arr.length; j++) { if (!compare(arr[j], arr[0])) {//与堆顶作比较，比堆顶大(小)则替换原堆顶，并堆化 [arr[j], arr[0]] = [arr[0], arr[j]]; adjustHeap(arr, 0, k, compare); } } return arr[0];//返回堆顶（topK） }
————————————————版权声明：本文为CSDN博主「Small Tornado」的原创文章，遵循CC 4.0 BY-sA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/XIAOLONGJUANFENG/article/details/114195541
以上是脚本宝典为你收集整理的堆排序以及TopK大顶堆小顶堆求解方式（js版）全部内容，希望文章能够帮你解决堆排序以及TopK大顶堆小顶堆求解方式（js版）所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。