大门|大门-CS-2003 |问题63

存储一组整数需要一个数据结构，以便在（logn）时间内完成以下每个操作，其中n是集合中的元素数。

   o    Delection of the smallest element 
   o    Insertion of an element if it is not already present in the set

以下哪种数据结构可用于此目的？ （A） 可以使用堆，但不能使用平衡的二进制搜索树 （B） 可以使用平衡二叉搜索树，但不能使用堆 （C） 平衡二叉搜索树和堆都可以使用 （D） 既不能使用平衡二叉搜索树，也不能使用堆 答复: （B） 说明： 首先，我们将讨论堆和平衡bst，以及它对基本操作的时间复杂性，如

插入、删除、查找。

堆：-

让我们把它看作是最小堆。

1） 插入：O（logn）

2） 删除Min:O（logn）（只需将root替换为INT_MAX和heapify）

3） 查找：O（n）

平衡BST：-

1） 插入：O（logn）

2） 删除最小值：O（logn）

3） 查找：O（logn）

报表1：

1） 在两种数据结构中，最小元素的删除都可以在O（logn）中完成

报表2：

1） 如果一个元素尚未出现在集合中，则插入该元素

在heap中，我们可以在O（n）中执行这个操作，因为我们必须在这里执行线性搜索，而在BST中，我们可以在O（logn）中执行这个操作

见本报告问题4 https://www.geeksforgeeks.org/data-structures-and-algorithms-set-3/

这个解决方案是由 阿尼尔·赛克里希纳·德瓦拉塞蒂 这个问题的小测验