數據結構網絡化用於獲取

Question

我試圖解決萬阿英，蔣達清第k值最大的種種疑問的規定：使支持數據結構：

1）添加元素與密鑰K

2）刪除與密鑰k元

3）打印數據結構第k最大元素

我認爲maxheap應該工作，但在這種情況下，我們需要刪除堆前k-1最大的價值，以獲得第k個最大的元素，所以它贏得在這裏工作。

我該如何解決這個問題？

Answer 1

你可以用一個order statistic tree來解決這個問題，它是一個（平衡）二叉樹，可以讓你在log（n）時間內用平衡樹找到第i個最小（或最大）元素。