查找任意樹中的n個最大節點

給定一棵任意樹（不是二叉樹），每個節點都標記爲一個整數。 如何找到樹中最大的n個節點？ 例如如果一棵樹包含{43,253,48,62,91,641}，並且要求3個最大的節點，那麼算法應該返回< 641,253,91>。查找任意樹中的n個最大節點

允許所有的C++（或任何語言）標準庫函數/數據結構。只要空間使用量不變，它也可以向節點添加字段。就像我可以給每個節點添加一個字段，讓它指向其最大的子節點，但是我不能讓ArrayList以排序的順序存儲它的所有子節點。

作爲一名新程序員，我在這個問題上花了好幾天的時間。一個簡單的圖形搜索算法（BFS，DFS）可以工作並且易於實現，但它們速度不夠快，因爲它們都在整個樹上進行徹底的搜索。

你能幫我找到一個正確和快速（呃）解決這個問題嗎？

來源

2017-08-20 BeLikeJo

如果樹是任意的，那麼您可能必須搜索所有節點以找到n個最大的節點。 – Cuber

@BeLikeJo：請注意，將字段添加到每個節點以指向最大的子節點與節點數量成線性關係。添加一個數組列表來存儲所有孩子的順序也與節點數量成線性關係。所以，你的限制（「恆定空間使用率」）有點奇怪。我也會注意到這兩個領域都不能解決你的問題。任意一棵樹最終可能成爲一棵樹，如果不碰到所有節點，這棵樹就不可能遍歷。我想沒有什麼能阻止每個節點擁有與樹無關的子節點，所以你真的在處理兩棵樹（其中之一是二進制）。 – Brian

作爲一名新程序員，我在這個問題上花了好幾天時間。一個簡單的圖形搜索算法（BFS，DFS）可以工作並且易於實現，但它們速度不夠快，因爲它們都在整個樹上進行徹底的搜索。

由於您的樹不是二叉樹，因此檢查節點不會產生有關其子節點的附加信息。因此，不可能實現產生K個最高值而不徹底搜索整個樹的算法。換句話說，你不會獲得比使用無序數組的無序數組更好的性能。

當您遍歷您的任意樹時，要獲得K值在O（N * log K）時間內保持K元素的priority queue。

來源

2017-08-20 15:56:24 dasblinkenlight

由於給定的樹是任意的，沒有特殊的屬性。要找到最高值的孩子，您需要搜索整個圖表。它的複雜性O（n）。

對於前K最高值的孩子，

你有一個O（N *登錄K）的時間 - 優先級隊列基礎的解決方案，如dasblinkenlight答覆中提到。

您還有一個O（N）時間解決方案，並且Median of Median也是如此。

來源

2017-08-21 06:56:42 arunk2

查找任意樹中的n個最大節點

回答

相關問題