'use strict';
//堆排序
//堆: 完全二叉树
//最大堆定义: 父节点>= 左子节点 父节点 >= 右子节点
//维持最大堆性质
function maxHeapify(arr, i, heapSize) {
let r = right(i); //右子节点
let l = left(i); //左子节点
let largest = i;
//求right,left和parent三者中最大者
if (r < heapSize && arr[r] > arr[i]) {
largest = r;
}
if (l < heapSize && arr[l] > arr[largest]) {
largest = l;
}
//如果三者最大者不是parent i,那么需要i和相应的最大者进行交换,以便维持最大堆性质
if (largest != i) {
//交换
let max = arr[largest];
arr[largest] = arr[i];
arr[i] = max;
//交换以后,子节点有可能违背了最大堆定义,所以需要递归处理子节点
maxHeapify(arr, largest, heapSize);
}
}
//i的右子节点下标
function right(i) {
return 2 * i + 2;
}
//i的左子节点下标
function left(i) {
return 2 * i + 1;
}
//构建最大堆
function buildMaxHeap(arr) {
for(var i=parseInt(arr.length / 2); i >= 0; i--) {
maxHeapify(arr, i, arr.length);
}
}
//使用最大堆排序
function maxHeapSort(arr) {
//因为最大数总是在堆顶,所以每次把堆顶最大数拿出来,然后重新构建最大堆,再把堆顶数拿出来,以此递归,就能拿到一个从小到大排列的数组
buildMaxHeap(arr);
let heapSize = arr.length;
for(var i=arr.length-1; i>0; i--) {
let max = arr[0];
arr[0] = arr[i];
arr[i] = max;
heapSize = heapSize - 1;
maxHeapify(arr, 0, heapSize);
}
}
//随机获取一个数组
function randNum() {
return parseInt(Math.random() * 100);
}
function getRandArr(length) {
var arr = [];
for(var i=0; i<length; i++) {
arr.push(randNum());
}
return arr;
}
var arr = getRandArr(10);
console.info("随机生成的数组:", arr);
maxHeapSort(arr);
console.info("用堆排序后数组:", arr);
//某次运行结果如下:
//随机生成的数组: [ 29, 92, 50, 89, 96, 64, 36, 47, 34, 96 ]
//用堆排序后数组: [ 29, 34, 36, 47, 50, 64, 89, 92, 96, 96 ]
© 著作权归作者所有
举报
打赏
0 赞
0 收藏
分享
加载中
其他人还在看
开源之道引言 本文翻译于一篇基于CC-By协议的论文，该论文最初发表在《International Free and Open Source Software Law Review》Vol. 5, Issue 1 中，作者是 Paula Hunter 和Stephen Walli。 开源之道打算在202......
简述 本篇中，我们将打开一个窗口并且在窗口（window）中显示帧率（framerate）。我使用的是Python3，IDE是安装了pydev的Eclipse。你可以选择你喜欢的IDE或者编辑器。 导入和运行pygame 你可以创建一个python文件...
本文是探索协程如何简化异步 UI 编程系列的第二篇。第一篇侧重理论分析，这一篇我们通过实践来说明如何解决实际问题。如果您希望回顾之前的内容，可以在这里找到——《在 View 上使用挂起函数》。 让我们学以致用...
摘要：Oracle数据库有时候不小心删除掉数据，想查询这些数据，或者恢复数据，就可以使用带有as of子句的select语句进行闪回查询。 PG粉有福了，下面介绍一种类似“闪回查询”插件 pg_dirtyread，可以读取未被vac...
前言 上一章我们已经实现了快速排序，在数据理想化的情况下，上一章的快排性能确实也不错，但如果数据比较极端的，快排的O(nlogn)就不太稳定了，本章将介绍几种快排应对极端数据下优化方案；以及介绍partition操作...
复制（在上一篇博客文章中介绍）已经发布了一段时间，并且是Apache HBase最常用的功能之一。使集群与不同的对等方复制数据是非常常见的部署，无论是作为DR策略还是简单地作为在生产/临时/开发环境之间复制数据的无...
简介：本文由网易云音乐实时计算平台研发工程师岳猛分享，主要从以下四个部分将为大家介绍 Flink + Kafka 在网易云音乐的应用实战： 背景 Flink + Kafka 平台化设计 Kafka 在实时数仓中的应用 问题 & 改进 直播回...
JDK7 分析 JDK7中当我们用头插法 对旧table数据重定位到新table的时候我们知道是会行程环的，环产生的核心函数transfer如下，其中重点关注部分以标出。 头插法正常情况下： 并发情况下，比如我有两个线程在同时进...
SoWhat：麦叔，最近面别的公司没？ 麦叔：上次面试失败桑心死我了，我沉淀了一礼拜面头条去了。 SoWhat：哎呦我去！麦叔你这头条都面上了，面了几轮，手写红黑树没？ 麦叔：刚刚两轮，一面红黑树轻松搞定了！面我...
Kubernetes 动手系列想通过一系列动手的 demo ，来帮助读者快速的理解上手 Kubernetes 一些运行机制。会包括如下内容： 手动部署 开发一个 operator 开发 webhook 开发 chart 包 开发 scheduler 开发 stroagecal...
