我不記得固定大小排序樹的數據結構

假設我想從任意數量的記錄中找出最低的10個值。當我遍歷記錄時，我將它們添加到結構中，直到它達到我的最大大小爲10.之後，每次添加一個不高於列表中最高記錄的記錄時，當前最高被刪除保留最大數量的記錄。或者更簡單地說，我該如何處理一個（可能非常大的）對象列表，並且只以一種有效的內存方式保存特定數量的對象？我不記得固定大小排序樹的數據結構

我似乎記得有某種數據結構可以做到這一點，但顯然我在Google上做的不好。我假設它的任何結構都會有一個java實現。

來源

2012-08-02 Dave Novelli

你可能可以調整一個'PriorityQueue'來獲得你要找的東西。 – 2012-08-02 17:30:25

不完全是我想到的（10年前的數據結構類有點模糊），但是這應該會有效果！謝謝 – 2012-08-02 17:49:04

這就是說，塞巴斯蒂安的答案是一個親密的表弟（'PriorityQueue'由一個堆支持） – 2012-08-02 17:51:40

一個簡單的方法來做到這將是實現一個max-heap（一binary heap，例如），並執行以下操作（僞代碼啊嗬！）：

List elms; // original elements 
Heap heap; // heap we store in 

for element e in elms: 
    push e onto heap 
    if heap contains more than 10 elements: 
     pop the max element from heap

在此之後，heap將包含10最小的元素。

假設二進制堆，tihs需要O(k)多餘空間和O(n lg k)時間，其中k是您想要的元素數。

來源

2012-08-02 17:43:16

如果您願意將所有N個值保存在內存中，則可以使用二進制最小堆對數組進行heapify。

它的構造需要O（n）攤銷時間，並取O（10 * log（10））的10個最小元素，即O（1）。

來源

2012-08-03 20:12:10

我不記得固定大小排序樹的數據結構

回答

相關問題