algorithm - 摊销分析和竞赛题，有什么问题吗？

Question

我遇到了一个本地竞赛问题，如下所示。

如果为空MIN-Heap，我们将执行n任意操作insert，delete（在最小堆中使用给定的删除位置）。什么是amortized analysisforinsert和delete？

I) 插入 O(log n)，删除 O(1)

II) 插入 O(log n)，删除 O(log n)

III) 插入 O(1)，删除 O(1)

IV) 插入 O(1)，删除 O(log n)

我认为这是这个问题的一个问题，因为没有定义堆的类型。我在谷歌上读到我们有一些堆的选项（1）和（4）。从专家的角度来看，我们可以用这个问题说can we select all options as True?

Answer 1

你是对的——这个问题是不正确的。Min heap 是一种抽象的数据结构，支持 push 和 popMin 操作，可以通过多种不同的方式实现。根据实现的不同，操作的复杂性会有所不同。在给定位置删除也不是类最小堆操作。除非问题中有更多的上下文，否则它的定义并不明确。