4 ms·
> To use the heap you still need to look up the words efficiently. Why? Just split the text and put everything into the heap, the heap algorithm will maintain
by KRAKRISMOTT 3y ago
> To use the heap you still need to look up the words efficiently.
Why? Just split the text and put everything into the heap, the heap algorithm will maintain the sorted order by rebalancing during insertion
- abecedarius 3y agoThe textbook solution I assume you meant, to find the most common k elements of a list, uses an updatable priority queue (heap). This orders the (key, count) pairs by the count. But that's a separate question from how you look up the key (i.e. given a word, find the pair whose count you want to increment), which is what Knuth's hash tries were for here.
- KRAKRISMOTT 3y agoThanks for the clarification