在最大二叉堆中插入 N 个数
Insert N numbers in a maximum binary heap
我已经创建了一个实现最大二叉堆的数据结构。我试图找到 2 个 n 数字序列，插入需要 O(n) 和 O(nlogn) 时间。
这可能吗？
让我试着重申一下你的问题；如有不妥请指正
因此 二叉堆 数据结构的时间复杂度为 logN 对应 insertion。在一个max-heap中插入的过程如下，
- 该树是一棵完全二叉树，即除最后一层外所有层都是满的。
- 在树的最左边插入。
- 如果节点小于父节点，则执行交换。
- 重复该过程，直到节点处于适当的级别。
所以对于你的问题，
你想要插入时间复杂度为 O(n) 的 n 个数字序列。这意味着，每次插入都需要 O(1) 或常数时间。这意味着我们需要一个不需要 heapify 操作的序列。我认为像下面这样的序列可以避免 heapify 操作的需要。
[10, 8, 9, 4, 5, 6, 7 ]
对于第二个，你想要 O(nlogn) 这意味着每个操作需要 logn 这是用于插入的二进制堆的标准或平均性能。所以任何序列都应该做，
[ 1, 2, 3, 4, 5, 6, 7]
对于从第 2 个开始的每个节点，您需要与父节点和 swap 进行比较。
我已经创建了一个实现最大二叉堆的数据结构。我试图找到 2 个 n 数字序列，插入需要 O(n) 和 O(nlogn) 时间。 这可能吗？
让我试着重申一下你的问题；如有不妥请指正
因此 二叉堆 数据结构的时间复杂度为 logN 对应 insertion。在一个max-heap中插入的过程如下，
- 该树是一棵完全二叉树，即除最后一层外所有层都是满的。
- 在树的最左边插入。
- 如果节点小于父节点，则执行交换。
- 重复该过程，直到节点处于适当的级别。
所以对于你的问题，
你想要插入时间复杂度为 O(n) 的 n 个数字序列。这意味着，每次插入都需要 O(1) 或常数时间。这意味着我们需要一个不需要 heapify 操作的序列。我认为像下面这样的序列可以避免 heapify 操作的需要。
[10, 8, 9, 4, 5, 6, 7 ]
对于第二个，你想要 O(nlogn) 这意味着每个操作需要 logn 这是用于插入的二进制堆的标准或平均性能。所以任何序列都应该做，
[ 1, 2, 3, 4, 5, 6, 7]
对于从第 2 个开始的每个节点，您需要与父节点和 swap 进行比较。