在排序堆的末尾插入一个元素需要 O(1)。但我想以这样的方式插入，使其保持排序。在 O(n) 中实现这一点并不是什么大问题。
我如何利用它已排序的优势？通过二分查找找到合适的位置需要 O(logn)。但是通过交换插入将再次是 n 阶。 如何降低时间复杂度？请帮忙。
最佳答案
这就是您通常插入堆的方式，这只是一个堆，而不是一个排序列表:
堆是分层结构。每个元素最多有 2 个子元素。要插入，只需在末尾追加，然后将其与其父元素进行比较，这可以由元素的位置确定。如果父元素更大，则将父元素与新元素交换。重复直到新元素大于其父元素，或者新元素成为第一个/顶部元素。这样，最小的元素始终是第一个元素。
此操作最多需要 O(log n) 次操作。
看完评论，你真正想要的不是经典的堆，而是使用指针或数组索引实现的排序树。搜索红黑树。
关于algorithm - 如何将元素插入已排序的堆中以使其保持排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30615025/