如何向排序堆中插入元素并保持其排序？

Question

3

在堆的末尾插入一个元素只需要 O(1) 的时间。但是我想以这样的方式插入，使其保持排序。在 O(n) 时间内实现这一点并不难。

如何利用它已经排序的特性呢？通过二分查找找到合适的位置只需要 O(logn) 的时间。但是通过交换进行插入仍然需要 O(n) 的时间。我该如何降低时间复杂度呢？请帮忙。

- cryptomanic

1

所以，与二叉堆没有任何关联，你只需将元素插入到排序数组中，数组应保持排序。这是在O(n)内完成的，无法避免。请参见wikipedia。您可能需要考虑使用其他数据类型，如二叉树或跳表。 - amit

你需要一种数据结构，它允许像链表或树一样进行廉价插入。（不是数组） - DrKoch

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zotta · Accepted Answer

这是正常情况下向堆中插入元素的方式，即只是一个堆而不是排序列表：

堆是一种分层结构。每个元素最多有两个子节点。要插入，只需将其附加在末尾，然后将其与其父节点进行比较，该父节点可以通过元素位置确定。如果父级更大，则交换父级和新元素。重复此操作，直到新元素大于其父元素或新元素已成为第一个/顶部元素。这样，最小的元素始终是第一个元素。

此操作最多需要O(log n)次操作。

阅读评论后，您实际上想要的不是经典堆，而是使用指针或数组索引实现的排序树。搜索 红黑树。