问题标签 [pairing-heap]

我尝试使用所有常规操作（合并、删除最小等）实现“配对堆”，然后我被要求编写一个函数，该函数将使用我新构建的堆实现对列表进行排序。不幸的是，似乎出了点问题……

以下是相关代码：

这些是一些可以帮助您理解代码的选择器：

现在让我们来解决问题：当我运行“heapsort”时，它会返回带有“void”的排序列表，如您所见：

..我该如何解决？

问候， Superguay

我刚刚实现了配对堆数据结构。Pairing heap 支持在 O(1) 摊销时间内插入、find-min、merge 和在 O(logN) 摊销时间内删除、delete-min。但最显着的操作是减少键，其复杂度为 O(log logN)。有关配对堆的更多信息，请访问http://en.wikipedia.org/wiki/Pairing_heap。

我已经实现了插入、合并和删除最小操作，但是维基百科文章没有说明如何减少给定节点的键，所以我无法实现。有人可以告诉我它实际上是如何工作的吗？

这是我的代码：

当我注意到在更多线程上使用独立优先级队列实际上会降低性能时，我试图使用工作线程来加速更大的算法。所以我写了一个小测试用例。

在其中我查询要启动多少个线程，将每个线程设置为自己的处理器，并从我的优先级队列中推送和弹出很多东西。每个线程都拥有自己的优先级队列，它们是单独分配的，所以我不怀疑错误共享。

我把测试用例放在这里，因为它比一个片段长。（处理器亲和位来自NCrunch）

优先级队列是我自己创建的，因为 .NET 没有内置队列。如果这有什么不同，它会使用配对堆。

无论如何，如果我用一个线程和一个核心运行程序，它的使用率大约是 100%。 两个线程/两个内核的使用率下降 最终所有 8 个内核的使用率下降到 30%。

这是一个问题，因为性能下降抵消了多线程带来的任何好处。是什么导致性能下降？每个队列完全独立于其他线程的

我正在阅读Pairing heap。

这很简单，唯一棘手的部分是delete_min操作。

唯一重要的基本操作是从堆中删除最小元素。标准策略首先从左到右成对合并子堆（这是给这个数据结构命名的步骤），然后从右到左合并生成的堆列表：

我认为我不需要在此处复制/粘贴代码，因为它位于 wiki 链接中。

我的问题是

1. 为什么他们做这两个通过合并？

2. 为什么他们首先合并对？不直接合并它们吗？

3. 还有为什么在合并对之后，专门从右到左合并？

我正在尝试通过代码进行配对，它仅适用于普通设备。如果我使用蓝牙扫描仪，它会与之配对，但设备无法工作，直到我进入 android 设置并选择输入设备复选框。我怎样才能通过代码做到这一点？

谢谢你。

这是我的配对代码：

我想知道自从我更新到 iOS8.2 以来我可以看到的 CoreBluetooth 中的一种行为。我认为它在 iOS 8.1 中可以正常工作

情况：

iPhone 6 iOS 8.2 作为 CentralManager 自定义 BLE 设备 (CC2541)

现在......当我第一次尝试读取加密特征时，我得到了预期的 iO​​S 配对请求窗口。但是，如果键入正确的配对密钥，读取请求将第一次失败。之后，启动第二个加密读取请求将成功。

这是 iOS 8.2 中的错误还是我很困惑？这里有人检测到同样的问题吗？！

谢谢...

下面我们面临匈牙利算法的多重赋值问题。

设想：

我们有100名学生和5门课程，学生可以优先投票。因此，每个学生都会被分配到一门特定的课程。

优先级从 1 到 5。1 最低，5 最高

原始数据如下所示：

显然行多于列。

我们面临的问题是：我们需要每列不止一个分配。

这是负责使用返回无效结果的匈牙利算法进行分配的 PHP 代码。

编辑：这是返回有效结果的 Sktip。

注意：请耐心等待，这是来自 Java 的低质量端口。

因此，该算法正在制作这个方阵，结果显示损坏的数据。

我考虑了多种解决方案。

根据列大小对矩阵进行切割，生成大量方形矩阵。这可能会破坏算法的主要功能。

另一种解决方案是尽可能多地分配，并在一个新的例程中处理其余的，直到没有更多的条目。

显然该算法还没有提供这种能力。

是否有可能在 MySQL 中执行此操作，因此原始数据存储在 MySQL DBS 中。

我正在为我的一门课程做作业，一个问题要求显示减少键操作，对于配对堆，需要 O(1) 时间。

显然，如果您有一个指向要减少的键的指针，那么该操作将花费 O(1) 时间（只需删除链接，更改键值，然后合并）。

但是，在分配中没有任何地方说我们得到了一个指向键的指针。如果我们没有得到一个指针，那么 reduce-key 就不可能花费 O(1) 时间（你必须先在堆中查找键，这不会花费恒定时间）。我看了文献，都说减少键需要 O(logn) 时间。

我在这里错过了什么吗？

我正在尝试实现一个配对堆（https://en.wikipedia.org/wiki/Pairing_heap），但我似乎在编写赋值运算符和复制构造函数时遇到了麻烦。我的默认构造函数以及我的 push 和 pop 函数似乎都可以工作。但是，当我尝试通过复制构造创建新堆或进行分配时，我会在复制期间或第一次后续操作时出现段错误。我已经包含了我认为是以下问题的相关代码段。如果有人能给我一些关于如何进行的建议，将不胜感激。

所以，我正在用 C++ 编写一件事，我正在尝试用配对堆实现一个优先级队列。我希望这个优先级随着时间的推移自动增加，这样如果元素（一个类）在堆中已经存在了 5 分钟，它的优先级（一个变量）就会增加。我不知道如何做到这一点。

我可以实现一个函数，在每个设定的时间内检查每个元素的持续时间，但问题是检查堆中的每个元素非常困难。所以我认为我需要在元素中做一些事情，但我不确定是什么以及如何做。

有什么简单的解决方案吗？我觉得我一定是错过了什么，但如果不是这样，那我最好放弃这个想法，因为我必须尽快完成这件事。

UP：这个程序是为人类排队的，所以这个想法的原因是不要让人们等待太久。优先级是任意的，添加每个元素时都会为每个元素设置优先级“级别”，因此将时间设为优先级不是我的解决方案。