堆是一种经典的数据结构，它将完整的二叉树(或广义版本的 d-ary)树放入一个连续的数组中，以广度优先遍历顺序存储元素。这样，树的同一级别的所有元素一个接一个地连续存储。
我正在实现一个数据结构，在底层，它是一个具有固定度 d 的完整平衡树，我想以连续的形式存储树以释放节点指针的空间。所以我想把节点放在堆中使用的广度优先顺序，但是我担心从根到叶的典型搜索的缓存性能，因为在每个级别 l，我跳过了很多元素。
有没有一种方法可以基于深度优先顺序来获得 d-ary 完整树的紧凑连续表示？
这样，在我看来，搜索叶子时接触到的节点更有可能彼此靠近。那么问题是如何检索节点的父节点和子节点的索引，但我也想知道树上的哪些操作在此设置中通常是有效的。
我正在用 C++ 实现这个东西，以防万一。
最佳答案
为简单起见，我将把我的讨论限制在二叉树上，但我所说的也适用于 n 叉树。
堆(和一般的树)以广度优先存储在数组中的原因是，以这种方式添加和删除项目要容易得多:增长和缩小树。如果您存储深度优先，则必须以最大预期大小分配树，或者在添加关卡时必须进行大量移动项目。
但是，如果您知道您将拥有一个完整、平衡的 n 元树，那么选择 BFS 或 DFS 表示在很大程度上取决于样式。就内存性能而言，两者并没有什么特别的好处。在一种表示 (DFS) 中，您将缓存未命中放在前面，而在另一种情况 (BFS) 中，您将缓存未命中放在最后。
考虑一棵具有 20 层(即 2^20 - 1 项)的二叉树，其中包含从 0 到 (2^20 - 1) 的数字。每个节点占用四个字节(整数大小)。
使用 BFS，当您获得树的第一个 block 时会导致缓存未命中。但是，您在缓存中拥有树的前四个级别。所以你接下来的三个查询保证在缓存中。之后，当节点索引大于 15 时，保证缓存未命中，因为左子节点位于 x*2 + 1 处，至少有 16 个位置(64 字节)远离 parent 。
使用 DFS，当您读取树的第一个 block 时会导致缓存未命中。只要您要搜索的数字在当前节点的左子树中，就可以保证前 15 个级别不会出现缓存未命中(即您不断向左移动)。但是任何正确的分支都会导致缓存未命中，直到您下降到叶子上方的三个级别。此时，整个子树将适合缓存，并且您的剩余查询不会导致缓存未命中。
使用 BFS，缓存未命中数与您必须搜索的级别数成正比。使用 DFS，缓存未命中的数量与通过树的路径和您必须搜索的层数成正比。但是平均而言，您在搜索项目时发生的缓存未命中次数对于 DFS 和 BFS 是相同的。
BFS 计算节点位置的数学比 DFS 更容易，尤其是当您想要找到特定节点的父节点时。
关于c++ - 我可以基于深度优先顺序而不是宽度优先顺序为完整的树提供类似堆的连续布局吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24308647/
类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc
我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123
使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta
查看Ruby的CSV库的文档，我非常确定这是可能且简单的。我只需要使用Ruby删除CSV文件的前三列，但我没有成功运行它。 最佳答案 csv_table=CSV.read(file_path_in,:headers=>true)csv_table.delete("header_name")csv_table.to_csv#=>ThenewCSVinstringformat检查CSV::Table文档:http://ruby-doc.org/stdlib-1.9.2/libdoc/csv/rdoc/CSV/Table.html
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
我发现ActiveRecord::Base.transaction在复杂方法中非常有效。我想知道是否可以在如下事务中从AWSS3上传/删除文件:S3Object.transactiondo#writeintofiles#raiseanexceptionend引发异常后，每个操作都应在S3上回滚。S3Object这可能吗？？ 最佳答案 虽然S3API具有批量删除功能，但它不支持事务，因为每个删除操作都可以独立于其他操作成功/失败。该API不提供任何批量上传功能(通过PUT或POST)，因此每个上传操作都是通过一个独立的API调用完成的
我将应用程序升级到Rails4，一切正常。我可以登录并转到我的编辑页面。也更新了观点。使用标准View时，用户会更新。但是当我添加例如字段:name时，它不会在表单中更新。使用devise3.1.1和gem'protected_attributes'我需要在设备或数据库上运行某种更新命令吗？我也搜索过这个地方，找到了许多不同的解决方案，但没有一个会更新我的用户字段。我没有添加任何自定义字段。 最佳答案 如果您想允许额外的参数，您可以在ApplicationController中使用beforefilter，因为Rails4将参数
我遵循了教程http://gettingstartedwithchef.com/,第1章。我的运行list是"run_list":["recipe[apt]","recipe[phpap]"]我的phpapRecipe默认Recipeinclude_recipe"apache2"include_recipe"build-essential"include_recipe"openssl"include_recipe"mysql::client"include_recipe"mysql::server"include_recipe"php"include_recipe"php::modul
我正在阅读SandiMetz的POODR，并且遇到了一个我不太了解的编码原则。这是代码:classBicycleattr_reader:size,:chain,:tire_sizedefinitialize(args={})@size=args[:size]||1@chain=args[:chain]||2@tire_size=args[:tire_size]||3post_initialize(args)endendclassMountainBike此代码将为其各自的属性输出1,2,3,4,5。我不明白的是查找方法。当一辆山地自行车被实例化时，因为它没有自己的initialize方法
我们的git存储库中目前有一个Gemfile。但是，有一个gem我只在我的环境中本地使用(我的团队不使用它)。为了使用它，我必须将它添加到我们的Gemfile中，但每次我checkout到我们的master/dev主分支时，由于与跟踪的gemfile冲突，我必须删除它。我想要的是类似Gemfile.local的东西，它将继承从Gemfile导入的gems，但也允许在那里导入新的gems以供使用只有我的机器。此文件将在.gitignore中被忽略。这可能吗？ 最佳答案 设置BUNDLE_GEMFILE环境变量:BUNDLE_GEMFI
