Re^3: Size-limited, fitness-based lists

wouldn't a heap grow to include all items first before you extract the relevant ones

Yes, but I don't see a way to avoid that and yet satisfy your requirement to include all of the members of a class even if that causes the "minimum" to be exceeded. For example, what do you think we should do if the input list consists of a million words all of exactly the same length? If the "size-limited" aspect of the need is strong enough to make us discard some of that set of values, then you need to specify your "cut-off" heuristics somehow.

I reckon we are the only monastery ever to have a dungeon stuffed with 16,000 zombies.

Comment on Re^3: Size-limited, fitness-based lists

Replies are listed 'Best First'.
Re^4: Size-limited, fitness-based lists (size, ties) by tye (Sage) on Aug 10, 2015 at 21:41 UTC
wouldn't a heap grow to include all items first before you extract the relevant ones Yes In general, no. The reason I use a heap for "top 10 of a huge list" is because you can get that result from a heap that never gets above a size of 10. If you allow for ties, then you only have to let the heap grow beyond 10 based on how many items are currently tied for 10th place, which usually means that the heap only ever gets slightly longer than 10 items. Start with an empty heap configured to keep the worst item at the head. For each item, if there are fewer than 10 items in the heap, then push the next item in. Else, if the item is worse than the item at the head of the heap, then simply discard the item. Else, if the new item is tied with the worst item, then push it onto a separate stack of tied items. Else, the new item is better than the worst item so replace the worst item with the new item and push it down, then compare the new worst item (the new head of the heap) with the item you just removed. If the new head is better than the old head, then discard the old head and empty the list of tied items. Otherwise, push the old head onto the list of tied items. - tye	[reply]

Replies are listed 'Best First'.

Re^4: Size-limited, fitness-based lists (size, ties)
by tye (Sage) on Aug 10, 2015 at 21:41 UTC

wouldn't a heap grow to include all items first before you extract the relevant ones
Yes

In general, no. The reason I use a heap for "top 10 of a huge list" is because you can get that result from a heap that never gets above a size of 10. If you allow for ties, then you only have to let the heap grow beyond 10 based on how many items are currently tied for 10th place, which usually means that the heap only ever gets slightly longer than 10 items.

Start with an empty heap configured to keep the worst item at the head. For each item, if there are fewer than 10 items in the heap, then push the next item in. Else, if the item is worse than the item at the head of the heap, then simply discard the item. Else, if the new item is tied with the worst item, then push it onto a separate stack of tied items. Else, the new item is better than the worst item so replace the worst item with the new item and push it down, then compare the new worst item (the new head of the heap) with the item you just removed. If the new head is better than the old head, then discard the old head and empty the list of tied items. Otherwise, push the old head onto the list of tied items.

- tye

[reply]