java - 编写一个可以处理具有 K 个子节点的堆的程序

Question

我研究过二进制堆，但我仍然对如何为这个程序做什么感到很困惑如果我能得到一些指导，我将非常感激我仍在学习 java 并且在这样做时遇到了很多麻烦。

k-ary heap 类似于二叉堆（其中 k = 2），但（除了一个可能的例外）非叶节点有 k 个子节点而不是 2 个子节点。将 k-ary heap 实现为任意 k ≥ 2 的最小优先级队列，以支持以下操作：

• insert (x)：将元素x 插入到堆中。

• extract-min()：移除并返回堆中键最小的元素。

k-ary heap 将使用一个预定义大小的数组来实现。还通过测量给定输入文件 k = 2、4、6、8、10 的情况下执行一系列操作所需的时间，研究数据结构在不同 k 值下的相对效率。在输入文件中，“IN”代表插入和“EX”代表提取最小操作。

Answer 1

二叉堆被实现为几乎完整（=完整）的二叉树。对于您的 k-ary 堆，您可能需要生成almost full k-ary tree[树中的所有级别都已满，除了最后一个，您从左到右填充树]，并重复与原始堆相同的操作，但使用每个节点超过 2 个子节点。

有了一些关于堆操作的知识，尤其是heapify上面的技巧和技巧，实现你的 k-ary 堆应该不会太难。

要将其实现为数组，只需遵循二叉树如何实现为数组，并在将完整的 k-ary 树实现为数组时遵循这些想法。