添加，刪除的O型插接件（LOGN）

我們被要求創建，在最壞的情況下運行在O（LOGN）的算法添加，刪除的O型插接件（LOGN）

的算法中包含3個功能：getmin();getmax();add();

首先彈出來自堆棧的最小元素，並返回它; getmax彈出堆棧中最大的元素，並返回它; 將放元素添加到堆棧上。

我在想一個RB樹;但我意識到這是很難實現我自己的（從零開始）。

還有其他的樹或數據結構不太複雜的實現和運行在O（logn）？

我可以只使用基本的Python操作（即只列出，..）

來源

2015-05-04 BioShock

實現此功能的經典方法是[堆]（http://en.wikipedia.org/wiki/Heap_%28data_structure%29）。 – cfh

@cfh你將如何實現一個支持清除min和max的堆？ – IVlad

這不是你的問題的答案，但你可以在O（1）中通過維護另一個臨時堆棧來獲得最小值，這個臨時堆棧將保存當前最小值的引用，類似地它可以獲得最大值。 – Rahul

我會建議一個Treap。在我看來，它是最容易實現的平衡二叉搜索樹，因爲你只需要2次基本旋轉。

要搜索給定的鍵值，在二叉搜索樹中應用標準二分搜索算法，忽略優先級。

要插入一個新的密鑰x到樹中，爲x生成一個隨機優先級y。在樹中二進制搜索x，並在葉子位置創建一個新節點，其中二進制搜索確定x的節點應該存在。然後，只要x不是樹的根，並且具有比其父z更大的優先級數，則執行樹旋轉，以反轉x和z之間的父子關係。

要從樹枝中刪除節點x，如果x是樹的葉子，只需將其刪除即可。如果x具有單個子z，則從樹中移除x並使z爲x的父親的子元素（或者如果x沒有父元素，則使z爲樹的根）。最後，如果x有兩個子元素，則將它在樹中的位置與其排序順序中的直接後繼元z的位置交換，導致以前的一種情況。在這最後一種情況下，交換可能會違反z的堆排序屬性，因此可能需要執行額外的旋轉以恢復此屬性。

獲取最小值和最大值可以通過從最小值開始一直向左移動，並且一直移動到最大值。

來源

2015-05-04 07:33:41 IVlad

添加，刪除的O型插接件（LOGN）

回答

相關問題