top k facebook friends of a user

dfs using a minheap.

// dfs, time: O(nlogk), space: O(k + logn + n)
[] top(user, k):
    if user == null || k < 0:
        throw
    if k == 0:
        return []
    best = new minheap(capacity: k)
    set visited = new
    visited.add(user)
    for friend in user.friends():
        top(friend, k, best, visited)
    return best

top(user, k, best, visited):
    if visited.has(user):
        return
    visited.add(user)
    if best.count() == k:
        if user.rating() > best.top().rating():
            best.displace(user)
    else:
        best.insert(user)
    for friend in user.friends():
        top(friend, k, best, visited)

minheap:
    insert(x):
    // return current top, replace it with x and heapify
    x displace(x):
    x top(): // or peek()

bfs.

// bfs, time: O(nlogk), space: O(k + n)
[] top(user, k):
    if user == null || k < 0:
        throw
    if k == 0:
        return []
    best = new minheap(capacity: k)
    set visited = new
    visited.add(user)
    q = new
    for friend in user.friends():
        q.enqueue(friend)
    top(k, best, q, visited)
    return best

top(k, best, q, visited):
    while !q.isEmpty():
        user = q.dequeue()
        if visited.has(user):
            continue
        visited.add(user)
        if best.count() == k:
            if user.rating() > best.top().rating():
                best.displace(user)
        else:
            best.insert(user)
        for friend in user.friends():
            q.enqueue(friend)