插入和洗掉許多大于/小于或等于給定值的元素的最快排序結構是什么？我將分幾個步驟來描述它：
- 起點 = [1,2,3]
- 新值 5 = [1,2,3,5]
- 下一個新值 4 = [1,2,3,4,5]
- 下一個新值 4 再次 = [1,2,3,4,4,5]（4 的處理方式相同）
- removeTail(4) = [1,2,3] （它回傳洗掉的元素：[4,4,5]
- removeHead(2) = [3]（它回傳洗掉的元素：[1,2]
該結構將從單執行緒訪問，記憶體消耗無關緊要。我想達到最快（至少 O(logN)）的復雜性。我想知道我是否應該使用一些 B 樹，但似乎重新平衡開銷太大，所以也許我應該嘗試跳過串列？
uj5u.com熱心網友回復：
如果您對這些操作中的每一個可能 的性能都滿意，那么簡單的概率跳過串列在這里聽起來很完美。O(logn)
插入和洗掉是跳過串列的本機。
RemoveTail()并且RemoveHead()只是找到元素，并將“在它之上”的所有內容（在它之上，我的意思是你用來查找元素的實際路徑）向左或向右修剪。每個這樣的操作都是O(logn)平均的，因為您只觸摸路徑中的節點（并且可能每個節點都相鄰）。
如果您想要確定性 - 這也可以完成，但是在保持確定性結構的同時洗掉元素和重新平衡會更加復雜，盡管并非不可能。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/478404.html
上一篇：謎題：相反顏色的兩個相鄰單元格
下一篇：最大堆未正確創建