在二叉最大堆中插入一个新元素

Question

考虑向MaxHeap中插入元素的过程，其中MaxHeap由数组表示。假设我们对新叶子到根的路径进行二分查找，寻找新插入元素的位置，比较次数为：

A) Θ(logn)

B) Θ(loglogn)

C) Θ(n)

D) Θ(nlogn)

============================================= ============================

假设我将最大堆设为

                               100
                              /    \
                            80       90
                            /\       /\
                           50 40    70 60

现在说我插入了一个新元素 250，它将添加到最后一个叶节点，如下所示 -

                                100
                              /    \
                            80       90
                            /\       /\
                           50 40    70 60
                           /
                          250

现在通过添加 250 个最大堆属性被违反，我必须调用 Max heaping 这将占用 O(log n)，但我的问题是现在数组未排序，如您所见最大堆，那么我们如何应用二分查找呢？

看到数组是 100|80|90|50|40|70|60|250 和从叶到根的路径
包含 100|80|50|250 的节点，这不是排序数组，那么，我们如何应用二进制搜索？

另一个问题 - 如果我添加了一个不会违反最大堆的新元素属性假设我添加了新元素 30，那么数组将按降序排序并且我可以应用二进制搜索。

那么，我应该如何在考试中解决这个问题？

Answer 1

堆数组明显没有排序

路径已排序，但要插入的最后一个节点除外。它被排序是因为在最大堆中任何节点都大于或等于它的子节点，并且由于路径是由子节点组成的，它们将按降序排列。在此设置中我们可以忽略的最后一个节点，因为我们知道它不合适。

所以题目要求你在路径上二分查找新节点插入的位置。路径的长度为 O(logN)。对 N 个元素进行二分查找的复杂度为 O(logN)。所以复杂度为 O(loglogN).

这不会产生正确的堆，它只会告诉您插入新节点的位置。您仍然必须沿着路径将每个节点移动到堆中更深的位置，这仍然是 O(logN)。

Answer 2

鉴于此最大堆：

                               100
                              /    \
                            80       90
                            /\       /\
                           50 40    70 60

您知道新元素 250 必须插入路径 [100, 80, 50] 的某处。你知道，因为在标准的堆插入方法中，你将新项添加到数组中的第一个空闲位置，然后将其向上筛选到堆中。在这种情况下，您将把它添加到位置 7，到根的路径是 7 -> 3 -> 1 -> 0.

如果您应用二进制搜索来确定项目将沿着该路径插入的位置，您会发现它必须在值 100 之前。

我认为这个问题旨在测试您对堆属性的了解。在 n 个项目的堆中，有 log(n) 个级别。我们称该值为 h。从根到最后一层的项目的路径将包含 h 个项目。众所周知，二进制搜索是 O(log n)。或者，在这种情况下，O(log h)。由于 h == log(n)，答案是 O(log log n)。

在二叉最大堆中插入一个新元素

Insertion of a new element in Binary Max Heap

arrays

algorithm

heap

data-structures