//HeapUtil.heapSort(arr)
class HeapUtil
{
public static void swap<T>(IList<T> list, int i, int j)
{
T tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
public static void adjustUp(IList<int> list, int idx)
{
int n = idx;
while(n != 0)
{
int parent = (n - 1) / 2;
if (list[n] < list[parent])
{
swap(list, n, parent);
n = parent;
}
else
break;
}
}
public static void adjustDown(IList<int> list, int idx)
{
int n = idx;
while (n < list.Count / 2)
{
int lchild = n * 2 + 1;
int smallest = n;
if(list[lchild] < list[smallest])
{
smallest = lchild;
}
int rchild = lchild + 1;
if(rchild < list.Count && list[rchild] < list[smallest])
{
smallest = rchild;
}
if (smallest == n)
break;
else
{
swap(list, smallest, n);
n = smallest;
}
}
}
public static void heapAdd(IList<int> list, int elem)
{
list.Add(elem);
adjustUp(list, list.Count - 1);
}
public static int heapRm(IList<int> list, int idx)
{
swap(list, idx, list.Count - 1);
int res = list[list.Count - 1];
list.RemoveAt(list.Count - 1);
adjustDown(list, idx);
return res;
}
public static void heapMake(IList<int> list)
{
for(int i = list.Count / 2 - 1; i >= 0; i--)
{
adjustDown(list, i);
}
}
public static void heapSort(IList<int> list)
{
heapMake(list);
IList<int> res = new List<int>();
while(list.Count != 0)
{
res.Add(heapRm(list, 0));
}
list.Clear();
foreach(var e in res) list.Add(e);
}
}
近期热议
推荐标签 标签
-
RESTful
30 引用 • 114 回帖 • 7 关注
一种软件架构设计风格而不是标准,提供了一组设计原则和约束条件,主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁,更有层次,更易于实现缓存等机制。
-
NGINX
315 引用 • 547 回帖 • 1 关注
NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。
-
Sublime
10 引用 • 5 回帖
Sublime Text 是一款可以用来写代码、写文章的文本编辑器。支持代码高亮、自动完成,还支持通过插件进行扩展。
-
LeetCode
209 引用 • 72 回帖
LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!
-
负能量
89 引用 • 1251 回帖 • 394 关注
上帝为你关上了一扇门,然后就去睡觉了....努力不一定能成功,但不努力一定很轻松 (° ー °〃)
-
思源笔记
26329 引用 • 109488 回帖 • 1 关注
思源笔记是一款隐私优先的个人知识管理系统,支持完全离线使用,同时也支持端到端加密同步。
融合块、大纲和双向链接,重构你的思维。
-
Swift
34 引用 • 37 回帖 • 559 关注
Swift 是苹果于 2014 年 WWDC(苹果开发者大会)发布的开发语言,可与 Objective-C 共同运行于 Mac OS 和 iOS 平台,用于搭建基于苹果平台的应用程序。
-
知乎
10 引用 • 66 回帖
知乎是网络问答社区,连接各行各业的用户。用户分享着彼此的知识、经验和见解,为中文互联网源源不断地提供多种多样的信息。
-
Notion
10 引用 • 77 回帖 • 1 关注
Notion - The all-in-one workspace for your notes, tasks, wikis, and databases.
-
C
86 引用 • 165 回帖
C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。
-
工具
300 引用 • 768 回帖
子曰:“工欲善其事,必先利其器。”
-
安全
199 引用 • 818 回帖
安全永远都不是一个小问题。
-
SQLServer
21 引用 • 31 回帖 • 2 关注
SQL Server 是由 [微软] 开发和推广的关系数据库管理系统(DBMS),它最初是由 微软、Sybase 和 Ashton-Tate 三家公司共同开发的,并于 1988 年推出了第一个 OS/2 版本。
-
InfluxDB
2 引用 • 103 关注
InfluxDB 是一个开源的没有外部依赖的时间序列数据库。适用于记录度量,事件及实时分析。
-
GAE
14 引用 • 42 回帖 • 824 关注
Google App Engine(GAE)是 Google 管理的数据中心中用于 WEB 应用程序的开发和托管的平台。2008 年 4 月 发布第一个测试版本。目前支持 Python、Java 和 Go 开发部署。全球已有数十万的开发者在其上开发了众多的应用。
- 链书
-
安装
132 引用 • 1184 回帖 • 2 关注
你若安好,便是晴天。
-
Netty
49 引用 • 33 回帖 • 43 关注
Netty 是一个基于 NIO 的客户端-服务器编程框架,使用 Netty 可以让你快速、简单地开发出一个可维护、高性能的网络应用,例如实现了某种协议的客户、服务端应用。
-
Visio
1 引用 • 2 回帖 • 2 关注
-
Quicker
37 引用 • 157 回帖 • 1 关注
Quicker 您的指尖工具箱!操作更少,收获更多!
-
学习
172 引用 • 540 回帖
“梦想从学习开始,事业从实践起步” —— 习近平
-
JRebel
26 引用 • 78 回帖 • 681 关注
JRebel 是一款 Java 虚拟机插件,它使得 Java 程序员能在不进行重部署的情况下,即时看到代码的改变对一个应用程序带来的影响。
-
Chrome
63 引用 • 289 回帖
Chrome 又称 Google 浏览器,是一个由谷歌公司开发的网页浏览器。该浏览器是基于其他开源软件所编写,包括 WebKit,目标是提升稳定性、速度和安全性,并创造出简单且有效率的使用者界面。
-
frp
17 引用 • 7 回帖 • 3 关注
frp 是一个可用于内网穿透的高性能的反向代理应用,支持 TCP、UDP、 HTTP 和 HTTPS 协议。
-
C++
108 引用 • 153 回帖
C++ 是在 C 语言的基础上开发的一种通用编程语言,应用广泛。C++ 支持多种编程范式,面向对象编程、泛型编程和过程化编程。
-
gRpc
11 引用 • 9 回帖 • 102 关注
-
脑图
32 引用 • 99 回帖
脑图又叫思维导图,是表达发散性思维的有效图形思维工具 ,它简单却又很有效,是一种实用性的思维工具。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于