Top K frequent words: heap versus bucket sort

Why this matters

A search box shows the five most common queries. A news site lists the ten most read stories. A spam filter looks at the twenty most common words in a message. Each of these tasks has two steps. First, count how often each item appears. Second, pick the top few by count. The first step is easy with a map from item to count. The second step has more than one good answer, and the choice affects how fast the program runs when the input is large.

This lesson builds the full solution in C++. It uses std::unordered_map for the counts, which is the hash map from the earlier lesson on unordered maps. Then it shows two ways to pick the top K: a heap that holds only K items, and buckets that group the words by count. It ends with a comparison of the costs. The heap pattern for top K was covered in the heaps module, so this lesson applies it to words and adds the bucket method.

Defining the problem

Take a list of words. Count how many times each word appears. Print the K words with the highest counts. When two words have the same count, print the one that comes first in alphabetical order.

Here is a small example. The input has 8 words and K is 3:

the cat and the dog and the bird

The counts are:

• the appears 3 times.
• and appears 2 times.
• cat, dog and bird each appear once.

The top 3 are the (3), and (2), and then one of the three words with count 1. The tie rule says alphabetical order wins, so the third word is bird. The output is:

the 3
and 2
bird 1

Two terms need a plain explanation before the code. A hash map is a container that stores pairs of a key and a value and finds a key quickly. In C++ it is std::unordered_map. A heap is a tree-shaped container that always gives fast access to its smallest or largest item. In C++ it is std::priority_queue.

Step one: count the words

Every solution starts with the same code. Read the words one at a time and add 1 to the count for each word. The ++counts[w] line works because operator[] creates the key with the value 0 if the key is new, and then the ++ adds 1.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
 
int main() {
    int n;
    cin >> n;
 
    unordered_map<string, int> counts;
    for (int i = 0; i < n; ++i) {
        string w;
        cin >> w;
        ++counts[w];
    }
 
    for (const auto& [word, count] : counts) {
        cout << word << ' ' << count << '\n';
    }
}

The loop at the end prints the pairs in whatever order the hash map keeps them. That order is not sorted, and it should not be relied on. The rest of the lesson picks the top K in a fixed order.

Reading each word and doing one map update costs about O(1) on average per word. Big-O notation is a short way to say how the work grows with the input size. O(1) means the cost stays about the same no matter how big the input is. If there are n words in total, counting costs about O(n). Let u stand for the number of different words. The counting step uses O(u) memory, one entry for each different word.

Method one: a heap that holds K words

The idea is the same as in the heaps lesson on top K numbers. Keep a heap of at most K entries. Push each word's count into the heap. If the heap grows past K, remove the weakest entry. At the end, the heap holds the K best entries.

The word "weakest" needs a precise meaning here. An entry is stronger when its count is higher. When two counts are equal, the entry with the alphabetically smaller word is stronger. The heap must always remove the weakest entry, so its top must be the weakest entry. A priority_queue puts the largest element on top, as decided by a comparison function. To make the weakest entry the largest, the comparison function must say that a stronger entry is "less than" a weaker one.

The comparison is written as a function that returns true when a is stronger than b:

bool stronger(const Entry& a, const Entry& b) {
    if (a.count != b.count) return a.count > b.count;
    return a.word < b.word;
}

The priority_queue takes the comparison as a type, so the function is wrapped in a small struct:

struct StrongerFirst {
    bool operator()(const Entry& a, const Entry& b) const { return stronger(a, b); }
};

The full program is below. Type this into the Input box:

8 3
the cat and the dog and the bird

The output is:

the 3
and 2
bird 1

The program first reads n and k. Then it counts the words. The heap loop runs once for each distinct word. Each push adds the word to the heap. If the heap now holds K + 1 entries, the weakest entry is removed. Because the heap never holds more than K + 1 entries, each push and pop costs O(log K) time. Here log K is the number of times K can be halved before it reaches 1, so it stays small even for a large K.

The final loop moves the entries out of the heap. Because the heap gives the weakest entry first, the vector is in weakest-to-strongest order. reverse flips it, so the strongest entry is printed first.

Trace the heap on the example. The distinct words are the, cat, and, dog and bird, although the hash map may visit them in any order. Suppose they are visited as cat, and, the, dog, bird. The heap keeps the three strongest entries seen so far. After cat (1) and and (2), the heap holds two entries, and nothing is removed. After the (3), the heap holds three entries. When dog (1) arrives, the heap has four entries, and the weakest one is removed. The weakest is dog (1), because cat comes before dog alphabetically and so is stronger. The heap now holds the, and and cat. When bird (1) arrives, the weakest entry among the, and, cat and bird is cat, because bird comes before cat alphabetically. Removing cat leaves the, and and bird, which is the correct answer. The order of visiting does not change the result, because the tie rule is a fixed comparison.

Method two: buckets indexed by count

The heap method does work for every distinct word, with a cost that depends on K. The bucket method uses a different idea. A count is a whole number, and a word cannot appear more times than there are words in the input. So counts lie between 1 and n. That means the counts can be used as positions in a list.

Create a list of n + 1 buckets, numbered 0 to n. Bucket c holds every word that appears exactly c times. Bucket 0 is never used, because every word that is in the map appears at least once. Filling the buckets is one pass over the distinct words. Choosing the answer is one pass from the highest count down to 1. The words in one bucket all have the same count, so only the alphabetical tie rule needs sorting, and only inside a bucket.

A bucket is a simple container of words. The lesson uses a vector of vectors of strings. A bucket is a spot for words that share the same count, so the name describes the sorting strategy, not a special C++ type.

vector<vector<string>> buckets(static_cast<size_t>(n) + 1);
for (const auto& [word, count] : counts) {
    buckets[static_cast<size_t>(count)].push_back(word);
}

Then walk the buckets from the highest count down:

const size_t wanted = static_cast<size_t>(k);
vector<pair<string, int>> best;
for (size_t c = static_cast<size_t>(n); c > 0 && best.size() < wanted; --c) {
    auto& group = buckets[c];
    sort(group.begin(), group.end());
    for (const auto& w : group) {
        if (best.size() == wanted) break;
        best.emplace_back(w, static_cast<int>(c));
    }
}

The loop stops as soon as best holds K words. The inner loop also stops when best is full, so a bucket that is only partly needed adds only the words that are needed. The sort call puts the words of one bucket in alphabetical order before they are taken. It runs only for buckets the loop reaches.

The full program, with the same input as before:

8 3
the cat and the dog and the bird

Its output is the same as the heap version:

the 3
and 2
bird 1

Trace the buckets for this input. The counts are the 3, and 2, and cat, dog, bird at 1. The buckets with n = 8 are numbered 0 to 8. Bucket 3 holds the. Bucket 2 holds and. Bucket 1 holds cat, dog and bird in whatever order the map visited them. Buckets 8 down to 4 are empty, so the loop skips them without adding anything. At bucket 3, the loop takes the, and best holds 1 word. At bucket 2, it takes and, and best holds 2 words. At bucket 1, the loop sorts bird, cat, dog into bird, cat, dog, takes bird, and then stops because best holds 3 words.

The bucket program does not need a heap at all. The time spent is spread across the steps. Filling the buckets touches each distinct word once. The loop from n down to 1 costs O(n) in the worst case, because it may visit every bucket number. The sorts cost O(b log b) for each bucket b that the loop reaches. The bucket sizes add up to u, so the sorting never costs more than sorting all distinct words.

Method three: sort everything, as a baseline

The simplest solution sorts all the distinct words by count and then by word, and prints the first K. It is shorter, and it is a useful comparison.

vector<pair<string, int>> all(counts.begin(), counts.end());
sort(all.begin(), all.end(), [](const auto& a, const auto& b) {
    if (a.second != b.second) return a.second > b.second;
    return a.first < b.first;
});

Sorting u items costs O(u log u). When K is much smaller than u, most of that sorting work is wasted, because only K items are printed. The heap method avoids this waste. The bucket method avoids the comparisons on counts altogether.

On the example input, the three methods give the same three lines. That is a useful check: when you write a faster method, compare its output with a simple method on small inputs.

Comparing the costs

Let n be the total number of words, u the number of distinct words, and k the number of words to print.

A few points are worth a careful read.

The heap method's cost depends on K, not on n. If K is 10 and there are a million distinct words, the heap holds at most 11 entries at any moment. A sort would have to order all million words.

The bucket method has no dependence on K for the filling step, but the scan from n downward can be slow when n is large and most buckets are empty. That scan costs O(n) even if only a few counts are non-zero. On a large input with a lot of distinct words, that cost is small compared with counting itself. On a short input with a huge n in the header, the scan wastes time. The bucket size is set by n, not by the actual maximum count, so using the largest count found in the map as the bucket limit would reduce that waste. The example program keeps the simple form so the bucket index is easy to check.

The heap method needs no assumptions about the counts. The bucket method depends on counts being whole numbers no larger than n. That is always true for counts of words, but the method would not fit a problem where each item has a weight such as a price.

Memory matters too. The heap holds at most K + 1 entries. The buckets hold every distinct word once, plus n + 1 empty vectors. Each empty vector object takes about 24 bytes on a 64-bit machine, so for a large n the bucket list alone uses noticeable memory even when K is small.

Common mistakes

Using a max-heap for the top K

A new programmer often reaches for a max-heap of all distinct words. That gives the correct answer, but the heap holds every word in memory at once, when only K are needed. The fix is the rule from the heaps lesson: to keep the K best, use a heap that puts the weakest entry on top, and drop that entry when the heap grows past K.

If the comparison is flipped by mistake, the program prints the wrong words. This is a real output from the heap program with the comparison written as stronger(b, a) instead of stronger(a, b), on the same input with K = 3:

dog 1
cat 1
bird 1

These are the three weakest words, not the three strongest. The program still runs without an error, so the mistake is only visible in the output.

Forgetting the tie rule

If the heap compares only counts, the tie between cat, dog and bird is decided by the order the hash map visited them. That order can change between compilers and between runs. The program then gives different answers for the same input. Every comparison in both programs includes the word as a second key, so the answer is always the same.

Making the bucket list one too small

Buckets are numbered from 0 to n, so the vector needs n + 1 entries. If the list has only n entries, a word that appears n times has no bucket to go into. For example, the input 3 1 followed by a a a has one word that appears 3 times. A list of size 3 has no bucket 3.

The [] operator in std::vector checks the index only when the library's assertion checks are on. On the Ubuntu g++ 15 used here, they are on by default. The program was built with g++ -std=c++20 -Wall on g++ 15 and run on this input. It stopped with this message:

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = std::vector<std::__cxx11::basic_string<char> >; _Alloc = std::allocator<std::vector<std::__cxx11::basic_string<char> > >; reference = std::vector<std::__cxx11::basic_string<char> >&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The exit code was 134, which means the program was stopped by an abort signal. The message is long, but the important part is the last line, Assertion '__n < this->size()' failed. It means an index was outside the vector. On other setups the same mistake can cause silent memory damage instead of a message, so it should be fixed in the code, not left to the library.

Comparing a heap of pairs with no comparison

A priority_queue of a struct needs a way to compare two items. If none is given, the code does not compile. The message names the missing operator. This is the real error from g++ 15 for a program that puts Entry into priority_queue<Entry> with no comparison:

/usr/include/c++/15/bits/stl_function.h:408:20: error: no match for ‘operator<’ (operand types are ‘const Entry’ and ‘const Entry’)

The fix is to pass the comparison struct as the third template argument, as the heap program does, or to define operator< for Entry. Passing the struct is clearer, because the order of the heap is then written in one place.

Counting with a map that was not reset

Reusing one unordered_map for two separate inputs keeps the counts from the first input. The second answer then includes words from the first. In a program that reads several test cases, create the map inside the loop that reads each case.

Practice

Exercise 1

Count how often each letter appears in the text banana bandana, ignoring spaces. Print the two letters that appear most often, using the same tie rule as this lesson.

Show the answer

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
 
int main() {
    string text = "banana bandana";
    unordered_map<char, int> freq;
    for (char ch : text) {
        if (ch != ' ') ++freq[ch];
    }
    vector<pair<char, int>> items(freq.begin(), freq.end());
    sort(items.begin(), items.end(), [](const auto& a, const auto& b) {
        if (a.second != b.second) return a.second > b.second;
        return a.first < b.first;
    });
    for (size_t i = 0; i < 2; ++i) {
        cout << items[i].first << ' ' << items[i].second << '\n';
    }
}

The output is a 6 and then n 4. The letter a appears 3 times in banana and 3 times in bandana, which makes 6. The letter n appears 2 times in each word, which makes 4.

Exercise 2

Change the heap program so it prints the K least frequent words instead of the K most frequent. Use the input 8 3 with the cat and the dog and the bird. Which three words are printed?

Show the answer

Change the call inside the comparison from stronger(a, b) to stronger(b, a). The heap then keeps the weakest entries, and the program prints dog 1, cat 1 and bird 1. Those are the three words with count 1 that the tie rule ranks last. The counts 2 and 3 are stronger than 1, so the and and are not kept.

Exercise 3

Predict the output of the bucket program for this input:

6 3
b a b c a c

Then check your answer by running the program.

Show the answer

Every word appears twice, so every word is in the same bucket. The program sorts that bucket alphabetically and prints the first three words. The output is:

a 2
b 2
c 2

The heap program prints the same lines for this input.

Exercise 4

The bucket program uses static_cast<size_t>(n) + 1 for the bucket count. Explain why + 1 is needed. Then give the number of buckets needed for an input with 12 words.

Show the answer

A count can be as large as n, and the bucket for count n must exist. Buckets are numbered from 0 to n, which is n + 1 buckets. For 12 words, the program needs 13 buckets. Bucket 0 is never filled, but it is kept so that the count can be used directly as the index.

Exercise 5

Explain why the bucket program sorts each bucket as it reaches it, instead of sorting all the words once at the start.

Show the answer

Only the buckets that the loop reaches need sorting. The loop stops after K words are chosen. If K is 3 and the highest count bucket already holds 3 words, the lower buckets are never sorted. Sorting everything first would cost more time when K is small. Each bucket holds words with one count, so the sort only has to decide the alphabetical order inside that bucket.

Summary

• Count words with an unordered_map from word to count. This step costs about O(1) per word.
• To keep the K best entries, use a heap whose top is the weakest entry. Drop the top whenever the heap holds more than K entries.
• Put the tie rule inside the comparison, so the same input always gives the same output.
• Buckets indexed by count avoid comparing counts, but they need n + 1 buckets and a scan from n down to 1.
• Sorting all distinct words is the simplest method and is a good check on the faster programs.