在數據結構中查找最大值最大值和最大鍵值

我有一個存儲大量任務的系統。每個任務都有以下參數：在數據結構中查找最大值最大值和最大鍵值

Time t  
Priority p

每個任務都有一個唯一的時間。這意味着沒有2個任務可以具有相同的時間參數。
但是，優先級不是唯一的。多個任務可以具有相同的優先級。

我需要設計一個系統，可以解決四種類型的查詢。每種查詢的概率是相同的。以下是該類型的查詢：

UpdateTask（T，P）
這個查詢希望系統在時間t設置任務的優先級，以優先p。如果任務在系統中不存在，則創建一個新任務。如果任務存在，其優先級會更新。
DeleteTask（t）
此查詢希望系統刪除與時間t關聯的任務。如果這樣的任務不存在於系統中，則不需要採取任何行動。
GetMaximumPriority（）和GetMinimumPriority（）
此查詢希望系統打印系統中可用任務的最小優先級和最大優先級。
GetPriorityofTaskAtMaximumTime（）
這個查詢希望系統打印有我需要設計數據結構此係統參數t（時間）

的最大值任務的優先級併爲這些數據結構實現算法。我需要在Java中實現這一點。

我的方法：創建一個HashMap，其中鍵爲時間和值作爲優先級。 HashMap允許我定時處理前兩個查詢。但最後兩個查詢的時間複雜度爲O(n)。

問：是否有更好的時間和空間高效的數據結構和算法來解決這個問題？我主要需要一種方法來解決這個問題。完全實施的代碼是沒有必要的。謝謝。

來源

2017-08-01 Dhumil Agarwal

爲什麼不試着自己想出一個結構，然後問這裏（如果你有問題）或在[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); 
     } 
    }

因此，您將避免操作中的線性複雜性。

來源

2017-08-01 12:15:30 DAle

一般認爲 - 可能會根據您的數據類型進行更改，我認爲您可以爲您的時間和優先級設置一種類型的Map數據類型，並以時間爲關鍵。無論何時您想要刪除數據，都可以使用時間作爲關鍵字進行搜索並刪除，同樣可以使用時間作爲關鍵字進行更新。

然後你可以有一個列表每個時間以及優先級，然後你可以按照你的需要對列表進行排序。

來源

2017-08-01 10:23:45 deepakl

感謝您的建議。當更新和刪除查詢出現時，我需要更新每個這樣的查詢的2個列表。所以，前兩種查詢的時間複雜度顯着增加。如何解決這個問題？ –

那麼這只是您的查詢的一般想法，您可以使用更好的數據類型，如deHaar建議您進行所需的改進。 – deepakl

您可以嘗試堆或PriorityQueue，它可以在O（1）中找到最小值和最大值，如here所述。
他們還刪除並提取O（log n）中的最小值和最大值，但搜索將停留在O（n）處。您可能必須爲您的任務類實施Comparator ...

來源

2017-08-01 10:26:24 deHaar

實際上，優先級隊列能夠在常量時間內（但不是兩者）提取最小或最大元素，並且還支持在對數時間（但不是兩者）中刪除最小或最大元素。您需要更復雜的結構來實現該目標（例如，散列和兩個堆的組合） –

在數據結構中查找最大值最大值和最大鍵值

回答

相關問題