結構比SortedSet更快地添加一個接一個，然後從最後訪問少量項目

Question

我正在經歷一個List<>，對每個項目執行一些操作，然後根據這些操作的結果，可能添加每一個到另一個數據結構，爲此我正在使用一個SortedSet<>。在此之後，我需要排序最高的n項目作爲列表。

我唯一要做的事情就是對這個SortedSet<>進行清理整個事情並重新開始。有什麼辦法可以讓我多出一點成績？

我看到this similar question海報能夠使用自定義紅黑樹（在他們的問題得到解答後）實現大約1/6的運行時間減少。但是，SortedSet已經不是一棵紅黑樹嗎？在這種情況下，通過創建我自己的數據結構來嘗試存儲性能提升是否值得？

Answer 1

您可以嘗試通過不爲您的程序不使用「付費」來獲得更好的性能：而不是使用保留所有元素排序的樹結構，您可以使用不排序元素的heap，但讓您在k * log(n)時間內提取k最大元素。

堆在插入和刪除時往往比平衡樹更快，並且它們也佔用連續的內存區域，這在某些情況下可能會提高「緩存友好性」。當然，加速並不是免費的：堆不支持快速排序或刪除頂部以外的項目。