在数据结构中查找最大值最大值和最大键值

问题描述：

我有一个存储大量任务的系统。每个任务都有以下参数：在数据结构中查找最大值最大值和最大键值

Time t  
Priority p

每个任务都有一个唯一的时间。这意味着没有2个任务可以具有相同的时间参数。
但是，优先级不是唯一的。多个任务可以具有相同的优先级。

我需要设计一个系统，可以解决四种类型的查询。每种查询的概率是相同的。以下是该类型的查询：

UpdateTask（T，P）
这个查询希望系统在时间t设置任务的优先级，以优先p。如果任务在系统中不存在，则创建一个新任务。如果任务存在，其优先级会更新。
DeleteTask（t）
此查询希望系统删除与时间t关联的任务。如果这样的任务不存在于系统中，则不需要采取任何行动。
GetMaximumPriority（）和GetMinimumPriority（）
此查询希望系统打印系统中可用任务的最小优先级和最大优先级。
GetPriorityofTaskAtMaximumTime（）
这个查询希望系统打印有我需要设计数据结构此系统参数t（时间）

的最大值任务的优先级并为这些数据结构实现算法。我需要在Java中实现这一点。

我的方法：创建一个HashMap，其中键为时间和值作为优先级。 HashMap允许我定时处理前两个查询。但最后两个查询的时间复杂度为O(n)。

问：是否有更好的时间和空间高效的数据结构和算法来解决这个问题？我主要需要一种方法来解决这个问题。完全实施的代码是没有必要的。谢谢。

为什么不试着自己想出一个结构，然后问这里（如果你有问题）或在[codereview]（如果你想要意见）？这看起来像你要么需要学习一些东西（最好通过自己尝试完成）或者它是你的工作（在这种情况下，你是为了努力获得金钱的，所以首先展示一下;））。 – Thomas

你的时间是什么样的？你可以在'Map '中使用它作为键值吗？ – deHaar

我认为最难的查询是Q4，您是否有关于此查询的更多信息？它是否需要实时完成，还是可以缓存一些查询并在批处理模式下处理它们？或者你知道时间的范围吗？如果您一次批量处理所有查询，则可以在O（lg n）时间内完成，但如果您想要实时结果似乎并不容易 –

答

一种可能的方法是维护两个索引：一个用于时间，一个用于优先级。让我们以固定时间firstKey()/lastKey()操作取两个平衡搜索树。我将使用TreeMap的接口，但它应该有一个类似于C++的std::map的实现（它只是在更新过程中将迭代器维护到第一个元素和最后一个元素）。

第一幅地图将是Map<Time, Priority> tasks，第二幅 - Map<Priority, Integer> priorities。每个现有优先级值的第二个映射存储具有此优先级值的任务数。因此，您可以使用tasks作为第四个查询，使用priorities作为第三个查询。

UpdateTask（T，P）

Priority oldp = tasks.put(t, p); 
if (oldp != null) { 
    decreasePriority(oldp);  
} 
increasePriority(p);

复杂度：O（的log（n））

DeleteTask活动（t）的

if (tasks.containsKey(t)) { 
    Priority oldp = tasks.get(t); 
    tasks.remove(t); 
    decreasePriority(oldp); 
}

复杂度：O（的log（n））

GetMaximumPriority（），GetMinimumPriority（）
```
return priorities.lastKey(); 

return priorities.firstKey();  
```
复杂度：O（1）（具有适当lastKey()/firstKey()实现，O(log(n))与java.util.TreeMap）。
GetPriorityofTaskAtMaximumTime（）
```
return tasks.lastEntry().getValue(); 
```
复杂度：O（1）（具有适当lastEntry()实现中，O(log(n))与java.util.TreeMap）

void increasePriority(p) { 
     if (priorities.hasKey(p)) { 
      priorities.put(p, priorities.get(p) + 1); 
     } else { 
      priorities.put(p, 1); 
     }  
    } 

    void decreasePriority(p) { 
     int count = priorities.get(p); 
     if (count > 1) { 
      priorities.put(p, count - 1); 
     } else { 
      priorities.remove(p); 
     } 
    }

因此，您将避免操作中的线性复杂性。

答

一般认为 - 可能会根据您的数据类型进行更改，我认为您可以为您的时间和优先级设置一种类型的Map数据类型，并以时间为关键。无论何时您想要删除数据，都可以使用时间作为关键字进行搜索并删除，同样可以使用时间作为关键字进行更新。

然后你可以有一个列表每个时间以及优先级，然后你可以按照你的需要对列表进行排序。

感谢您的建议。当更新和删除查询出现时，我需要更新每个这样的查询的2个列表。所以，前两种查询的时间复杂度显着增加。如何解决这个问题？ –

那么这只是您的查询的一般想法，您可以使用更好的数据类型，如deHaar建议您进行所需的改进。 – deepakl

答

您可以尝试堆或PriorityQueue，它可以在O（1）中找到最小值和最大值，如here所述。
他们还删除并提取O（log n）中的最小值和最大值，但搜索将停留在O（n）处。您可能必须为您的任务类实施Comparator ...

实际上，优先级队列能够在常量时间内（但不是两者）提取最小或最大元素，并且还支持在对数时间（但不是两者）中删除最小或最大元素。您需要更复杂的结构来实现该目标（例如，散列和两个堆的组合） –

在数据结构中查找最大值最大值和最大键值

相关推荐