| 词条 | 堆 |
| 释义 | § 词语解释 堆 duī 【释义】 ①把东西聚集在一起：堆放｜堆积｜堆雪人。②堆积成的东西：土堆｜草堆｜垃圾堆。③量词，用于成堆的物或成群的人：一堆人｜一堆草｜一堆土。 【堆积】#duījī成堆地聚集：堆积如山。 〖例句〗眼看季节就要过了，仓库里卖不出去的货物仍堆积成山，只好削价处理。 【堆砌】 #duīqì ①垒筑。②比喻文章里使用大量不必要的词：堆砌辞藻。 〖例句〗写作文切忌堆砌华丽的辞藻。 ===================关于这个字的更多的信息================= 堆 <名> 堆 (象形。从土,隹声。本义:土堆) 土墩,沙墩或水中聚集的礁石 逾陇堆兮渡漠。――《楚辞·疾世》 激堆埼。――司马相如《上林赋》 呼水中沙堆为墠。――《尔雅·释水》注 又如:堆阜(小丘);堆埼(曲折的岸边)――多用于地名。如:滟滪堆(在四川长江中);双堆集(在安徽) 常为排列的整齐有序的叠堆 堆 <动> 堆积 堆,聚土。――《说文》 又如:堆堵(堆积堵塞);堆绢(堆纱花。用彩绢制成花鸟人物形状 堆 duī ①把东西聚拢在一起：～放粮食。 ②聚拢在一起的东西：粮食～。 ③量词。用于成堆的东西或成群的人：一～粮食、一～人。 【堆砌】垒积砖石并用泥灰粘合。比喻写文章时不必要地使用大量华丽的词语。 堆zuī 1.犹堆(duī)。归里包堆，方言，意为总计。 § 堆 程序 在程序中，堆用于动态分配和释放程序所使用的对象。在以下情况中调用堆操作： 1.事先不知道程序所需对象的数量和大小。 2.对象太大，不适合使用堆栈分配器。 堆使用运行期间分配给代码和堆栈以外的部分内存。 传统上，操作系统和运行时库随附了堆实现。当进程开始时，操作系统创建称为进程堆的默认堆。如果没有使用其他堆，则使用进程堆分配块。语言运行时库也可在一个进程内创建单独的堆。（例如，C 运行时库创建自己的堆。）除这些专用堆外，应用程序或许多加载的动态链接库 (DLL) 之一也可以创建并使用单独的堆。Win32 提供了一组丰富的 API 用于创建和使用专用堆。有关堆函数的优秀教程，请参阅 MSDN 平台 SDK 节点。 当应用程序或 DLL 创建专用堆时，这些堆驻留于进程空间中并且在进程范围内是可访问的。某一给定堆分配的任何数据应为同一堆所释放。（从一个堆分配并释放给另一个堆没有意义。） 在所有虚拟内存系统中，堆位于操作系统的虚拟内存管理器之上。语言运行时堆也驻留在虚拟内存之上。某些情况下，这些堆在操作系统堆的上层，但语言运行时堆通过分配大的块来执行自己的内存管理。绕开操作系统堆来使用虚拟内存函数可使堆更好地分配和使用块。 典型的堆实现由前端分配器和后端分配器组成。前端分配器维护固定大小块的自由列表。当堆收到分配调用后，它尝试从前端列表中查找自由块。如果此操作失败，则堆将被迫从后端（保留和提交虚拟内存）分配一个大块来满足请求。通常的实现具有每个块分配的开销，这花费了执行周期，也减少了可用存储区。 Windows NT 的实现（Windows NT 4.0 版及更高版本）使用 127 个从 8 到 1,024 字节不等的 8 字节对齐块的自由列表和 1 个混合列表。混合列表（自由列表【0】）包含大小超过 1,024 字节的块。自由列表包含在双向链接表中链接在一起的对象。默认情况下，进程堆执行合并操作。（合并操作是组合相邻的自由块以生成更大的块的操作。）合并操作花费了额外的周期，但减少了堆块的内部碎片。 单个全局锁可防止多线程同时使用堆。此锁主要用于保护堆数据结构不受多线程的任意访问。当堆操作过于频繁时，此锁会对性能造成负面影响。 § 堆的建立 1、算法思想： 不必将值一个个地插入堆中，通过交换形成堆。假设根的左、右子树都已是堆，并且根的元素名为R。这种情况下，有两种可能： (1) R的值小于或等于其两个子女，此时堆已完成； (2) R的值大于其某一个或全部两个子女的值，此时R应与两个子女中值较小的一个交换，结果得到一个堆，除非R仍然大于其新子女的一个或全部的两个。这种情况下，我们只需简单地继续这种将R“拉下来”的过程，直至到达某一个层使它小于它的子女，或者它成了叶结点。 2、筛选法： 首先将要排序的所有关键码放到一棵完全二叉树的各个结点中（这时的完全二叉树并不具备堆的特性）。显然，所有的结点Ki都没有子女结点，因此以这样的Ki为根的子树已经是堆，然后从 的结点Ki开始，逐步把以为根的子树排成堆，直到以K0为根的子树排成堆，就完成了建堆过程。 在考虑将以Ki为根的子树排成堆时，以Ki 1，Ki 2，…，Kn-1为根的子树已经是堆，所以这时如果有Ki≤K2i 1和Ki≤K2i 2，则不必改变任何结点的位置，以Ki为根的子树就已经是堆；否则就要适当调整子树中结点的位置以满足堆的定义。由于Ki的左、右子树都已经是堆，根结点是堆中最小的结点，所以调整后Ki的值必定是原来K2i 1和K2i 2中较小的一个。不妨假定K2 1较小，将Ki与K2i 1交换位置，这样调整后Ki≤K2i，Ki≤K2i 1，并且以K2i 2为根的子树原来已经是堆，不必再作任何调整，只有以K2i 1为根的子树由于K2i 1的值已经发生变化（与Ki交换了），所以有可能不满足堆的定义（当K2i 1的左、右子树已经是堆）。这时可重复上述过程，考虑将K2i 1以为根的子树排成堆。如此一层一层递推下去，最多可以一直进行到树叶。由于每步都保证将子树中最小的结点交换到子树的根部，所以这个过程是不会反馈的。它就像过筛一样，把最小的关键码一层一层选择出来。 建堆效率： n个结点的堆，高度d = 。根为第0层，则第i层结点个数为2i，考虑一个元素在堆中向下移动的距离。大约一半的结点深度为d-1，不移动（叶）。四分之一的结点深度为d-2，而它们至多能向下移动一层。树中每向上一层，结点的数目为前一层的一半，而子树高度加一。 这种算法时间代价为Ο(n) 由于堆有log n层深，插入结点、删除普通元素和删除最小元素的平均时间代价和最差时间代价都是 Ο(log n)。 § 相关条目 汉字 语言 词汇 |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。