Find the top X frequent numbers in a stream

gistfile1.txt

//Find the top X frequent numbers in a stream 
// http://www.cs.berkeley.edu/~satishr/cs270/sp11/rough-notes/Streaming-two.pdf

// Returns the top numbers k and their frequencies in the set
// Complexity:
//    space = O(k)
//    time = O(N)
map<int, int> getFreq(k, Set) {
    A = map<int, int>
    for (k : getTop(k, Set) {
        A[k] = (select i in Set where i == k).Count()
    }
    return A
}

// This function returns the top k numbers in the set S
// Complexity:
//    space = O(k)
//    time = O(N)
List<int> getTop(k, Set) {
    auto A = map<int, int>
    for (i : Set) {
        if (A.size() < k) {
            A[i] = 1
        } else if (A.contains(i)) {
            A[i] += 1 // increment its frequency
        } else {
            for (t : A.keys) {
                if (A[t] == 0)
                A.remove(t)
            }
            if (A.size() < X) {
                A[i] = 1
            } else  {
                for (t : A.keys) {
                    A[t] -= 1; // decrement frequency
                }
            }
        }
    }
    return A.keys
}