Der effizienteste Weg, um die häufigsten K-Wörter in einer großen Wortfolge zu finden

Eingabe: Eine positive ganze Zahl K und ein großer Text. Der Text kann tatsächlich als Wortfolge angesehen werden. Wir müssen uns also keine Gedanken darüber machen, wie wir es in Wortfolgen aufteilen können.
Ausgabe: Die häufigsten K Wörter im Text.

Mein Denken ist so.

1. Verwenden Sie eine Hash-Tabelle, um die Häufigkeit aller Wörter aufzuzeichnen, während Sie die gesamte Wortfolge durchlaufen. In dieser Phase ist der Schlüssel "Wort" und der Wert ist "Wortfrequenz". Dies dauert O (n) Zeit.

2. sortiere das (Wort, Wort-Frequenz) Paar; und der Schlüssel ist "Worthäufigkeit". Dies dauert bei normalem Sortieralgorithmus O (n * lg (n)).

3. Nach dem Sortieren nehmen wir nur die ersten K Wörter. Dies dauert O (K) Zeit.

Zusammenfassend ist die Gesamtzeit O (n + n lg (n) + K) ， Da K sicherlich kleiner als N ist, ist es tatsächlich O (n lg (n)).

Wir können das verbessern. Eigentlich wollen wir nur Top-K-Wörter. Mit anderen Worten, die Häufigkeit ist für uns nicht von Belang. Wir können also "partielle Heap-Sortierung" verwenden. In Schritt 2) und 3) sortieren wir nicht nur. Stattdessen ändern wir es so

2 ') einen Haufen von (Wort-, Wortfrequenz-) Paaren mit "Wortfrequenz" als Schlüssel aufbauen. Es dauert O (n) Zeit, um einen Heap zu erstellen;

3 ') extrahiere die obersten K Wörter aus dem Haufen. Jede Extraktion ist O (lg (n)). Die Gesamtzeit beträgt also O (k * lg (n)).

Zusammenfassend kostet diese Lösung Zeit O (n + k * lg (n)).

Das ist nur mein Gedanke. Ich habe keinen Weg gefunden, um Schritt 1) ​​zu verbessern.
Ich hoffe, dass einige Experten für Information Retrieval mehr Licht in diese Frage bringen können.

Dies kann in O (n) Zeit erfolgen

Lösung 1:

Schritte:

1. Zähle die Wörter und hashe sie, was in der Struktur wie dieser endet

   var hash = {
     "I" : 13,
     "like" : 3,
     "meow" : 3,
     "geek" : 3,
     "burger" : 2,
     "cat" : 1,
     "foo" : 100,
     ...
     ...
   

2. Durchlaufen Sie den Hash und suchen Sie das am häufigsten verwendete Wort (in diesem Fall "foo" 100). Erstellen Sie dann das Array dieser Größe

3. Dann können wir den Hash erneut durchlaufen und die Anzahl der vorkommenden Wörter als Array-Index verwenden. Wenn der Index nichts enthält, erstellen Sie ein Array, und fügen Sie es dem Array hinzu. Dann erhalten wir ein Array wie:

     0   1      2            3                  100
   [[ ],[cat],[burger],[like, meow, geek],[]...[foo]]
   

4. Dann durchlaufen Sie einfach das Array vom Ende und sammeln die k Wörter.

Lösung 2:

Schritte:

1. Das gleiche wie oben
2. Verwenden Sie min heap und halten Sie die Größe von min heap auf k. Für jedes Wort im Hash vergleichen wir das Vorkommen von Wörtern mit min. 1) Wenn es größer als der min-Wert ist, entfernen Sie min (wenn die Größe von min heap ist gleich k) und füge die Zahl in den min heap ein. 2) Ruhe einfache Bedingungen.
3. Nach dem Durchlaufen des Arrays konvertieren wir einfach den min-Heap in ein Array und geben das Array zurück.

Sie erhalten im Allgemeinen keine bessere Laufzeit als die von Ihnen beschriebene Lösung. Sie müssen mindestens O (n) arbeiten, um alle Wörter zu bewerten, und dann O (k) zusätzliche Arbeit, um die Top-k-Begriffe zu finden.

Wenn Ihr Problem sehr groß ist, können Sie eine verteilte Lösung wie Map / Reduce verwenden. Lassen Sie n Kartenarbeiter die Häufigkeit auf jeweils 1 / n des Textes zählen und senden Sie sie für jedes Wort an einen der m Reduzierer, die anhand des Hash des Wortes berechnet wurden. Die Reduzierer summieren dann die Zählungen. Wenn Sie die Sortierung über die Ausgänge der Reduzierungen zusammenführen, erhalten Sie die beliebtesten Wörter in der Reihenfolge ihrer Beliebtheit.

Eine kleine Variation Ihrer Lösung ergibt einen O (n) -Algorithmus, wenn es uns nicht darum geht, die oberste K zu klassifizieren, und eine O (n + k * lg (k)) - Lösung, wenn wir dies tun. Ich glaube, diese beiden Grenzen sind innerhalb eines konstanten Faktors optimal.

Die Optimierung erfolgt hier erneut, nachdem wir die Liste durchlaufen und in die Hash-Tabelle eingefügt haben. Wir können den Median des Median- Algorithmus verwenden, um das k-te größte Element in der Liste auszuwählen. Dieser Algorithmus ist nachweislich O (n).

Nachdem wir das kleinste K-te Element ausgewählt haben, teilen wir die Liste genau wie bei Quicksort um dieses Element auf. Dies ist offensichtlich auch O (n). Alles auf der "linken" Seite des Pivots befindet sich in unserer Gruppe von K Elementen, also sind wir fertig (wir können einfach alles andere wegwerfen, während wir weitergehen).

Diese Strategie lautet also:

1. Gehen Sie jedes Wort durch und fügen Sie es in eine Hash-Tabelle ein: O (n)
2. Wählen Sie das K-te kleinste Element aus: O (n)
3. Partition um dieses Element: O (n)

Wenn Sie die K-Elemente einordnen möchten, sortieren Sie sie einfach mit einer effizienten Vergleichssortierung in O (k * lg (k)), was eine Gesamtlaufzeit von O (n + k * lg (k)) ergibt.

Die O (n) -Zeitgrenze ist innerhalb eines konstanten Faktors optimal, da wir jedes Wort mindestens einmal untersuchen müssen.

Die zeitgebundene O (n + k * lg (k)) - Zeit ist ebenfalls optimal, da es keine vergleichsbasierte Möglichkeit gibt, k Elemente in weniger als k * lg (k) Zeit zu sortieren.

Wenn Ihre "große Wortliste" groß genug ist, können Sie einfach eine Stichprobe erstellen und Schätzungen abrufen. Ansonsten mag ich Hash-Aggregation.

Bearbeiten :

Mit Beispiel meine ich, wählen Sie eine Teilmenge von Seiten und berechnen Sie das häufigste Wort auf diesen Seiten. Vorausgesetzt, Sie wählen die Seiten in angemessener Weise aus und wählen eine statistisch signifikante Stichprobe aus, sollten Ihre Schätzungen der häufigsten Wörter angemessen sein.

Dieser Ansatz ist wirklich nur dann sinnvoll, wenn Sie so viele Daten haben, dass die Verarbeitung einfach nur albern ist. Wenn Sie nur ein paar Megabyte haben, sollten Sie in der Lage sein, die Daten zu durchbrechen und eine genaue Antwort zu berechnen, ohne ins Schwitzen zu geraten, anstatt sich die Mühe zu machen, eine Schätzung zu berechnen.

Sie können die Zeit weiter verkürzen, indem Sie mit dem ersten Buchstaben von Wörtern partitionieren und dann den größten Mehrwortsatz mit dem nächsten Zeichen partitionieren, bis Sie k Einzelwortsätze haben. Sie würden eine Art 256-Wege-Baum mit Listen von Teil- / vollständigen Wörtern an den Blättern verwenden. Sie müssen sehr vorsichtig sein, um nicht überall String-Kopien zu verursachen.

Dieser Algorithmus ist O (m), wobei m die Anzahl der Zeichen ist. Es vermeidet diese Abhängigkeit von k, was für große k sehr schön ist [da Ihre angegebene Laufzeit falsch ist, sollte es O (n * lg (k)) sein, und ich bin mir nicht sicher, was das bedeutet m].

Wenn Sie beide Algorithmen nebeneinander ausführen, erhalten Sie einen asymptotisch optimalen O-Algorithmus (min (m, n * lg (k))), der meiner Meinung nach im Durchschnitt schneller sein sollte, da er nicht involviert ist Hashing oder Sortieren.

Ihre Beschreibung enthält einen Fehler: Das Zählen dauert O (n), das Sortieren jedoch O (m * lg (m)), wobei m die Anzahl der eindeutigen Wörter ist. Dies ist normalerweise viel kleiner als die Gesamtzahl der Wörter, daher sollte wahrscheinlich nur optimiert werden, wie der Hash erstellt wird.

Ihr Problem ist dasselbe wie dieses: http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

Verwenden Sie Trie und Min Heap, um es effizient zu lösen.

Wenn Sie nach der Liste der k häufigsten Wörter in Ihrem Text für ein praktisches k und für eine natürliche Sprache suchen, ist die Komplexität Ihres Algorithmus nicht relevant.

Nur Probe , sagen wir, ein paar Millionen Wörter aus dem Text, Verfahren , dass mit jedem Algorithmus in einer Angelegenheit von Sekunden , und die häufigsten Zählungen sehr genau sein.

Als Randnotiz ist die Komplexität des Dummy-Algorithmus (1. alle zählen 2. die Zählungen sortieren 3. die besten nehmen) O (n + m * log (m)), wobei m die Anzahl der verschiedenen Wörter in Ihrem ist Text. log (m) ist viel kleiner als (n / m), also bleibt es O (n).

Praktisch zählt der lange Schritt.

1. Verwenden Sie eine speichereffiziente Datenstruktur, um die Wörter zu speichern
2. Verwenden Sie MaxHeap, um die häufigsten K-Wörter zu finden.

Hier ist der Code

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import com.nadeem.app.dsa.adt.Trie;
import com.nadeem.app.dsa.adt.Trie.TrieEntry;
import com.nadeem.app.dsa.adt.impl.TrieImpl;

public class TopKFrequentItems {

private int maxSize;

private Trie trie = new TrieImpl();
private PriorityQueue<TrieEntry> maxHeap;

public TopKFrequentItems(int k) {
    this.maxSize = k;
    this.maxHeap = new PriorityQueue<TrieEntry>(k, maxHeapComparator());
}

private Comparator<TrieEntry> maxHeapComparator() {
    return new Comparator<TrieEntry>() {
        @Override
        public int compare(TrieEntry o1, TrieEntry o2) {
            return o1.frequency - o2.frequency;
        }           
    };
}

public void add(String word) {
    this.trie.insert(word);
}

public List<TopK> getItems() {

    for (TrieEntry trieEntry : this.trie.getAll()) {
        if (this.maxHeap.size() < this.maxSize) {
            this.maxHeap.add(trieEntry);
        } else if (this.maxHeap.peek().frequency < trieEntry.frequency) {
            this.maxHeap.remove();
            this.maxHeap.add(trieEntry);
        }
    }
    List<TopK> result = new ArrayList<TopK>();
    for (TrieEntry entry : this.maxHeap) {
        result.add(new TopK(entry));
    }       
    return result;
}

public static class TopK {
    public String item;
    public int frequency;

    public TopK(String item, int frequency) {
        this.item = item;
        this.frequency = frequency;
    }
    public TopK(TrieEntry entry) {
        this(entry.word, entry.frequency);
    }
    @Override
    public String toString() {
        return String.format("TopK [item=%s, frequency=%s]", item, frequency);
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + frequency;
        result = prime * result + ((item == null) ? 0 : item.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        TopK other = (TopK) obj;
        if (frequency != other.frequency)
            return false;
        if (item == null) {
            if (other.item != null)
                return false;
        } else if (!item.equals(other.item))
            return false;
        return true;
    }

}   

}}

Hier sind die Unit-Tests

@Test
public void test() {
    TopKFrequentItems stream = new TopKFrequentItems(2);

    stream.add("hell");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hero");
    stream.add("hero");
    stream.add("hero");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("home");
    stream.add("go");
    stream.add("go");
    assertThat(stream.getItems()).hasSize(2).contains(new TopK("hero", 3), new TopK("hello", 8));
}

Weitere Einzelheiten finden Sie in diesem Testfall

1. Verwenden Sie eine Hash-Tabelle, um die Häufigkeit aller Wörter aufzuzeichnen, während Sie die gesamte Wortfolge durchlaufen. In dieser Phase ist der Schlüssel "Wort" und der Wert ist "Wortfrequenz". Dies dauert O (n) Zeit. Dies ist das gleiche wie bei jedem oben erläuterten

2. Behalten Sie beim Einfügen in die Hashmap das Treeset (spezifisch für Java, es gibt Implementierungen in jeder Sprache) der Größe 10 (k = 10) bei, um die 10 häufigsten Wörter beizubehalten. Bis die Größe weniger als 10 beträgt, fügen Sie sie hinzu. Wenn die Größe gleich 10 ist, wenn das eingefügte Element größer als das minimale Element ist, dh das erste Element. Wenn ja, entfernen Sie es und fügen Sie ein neues Element ein

Informationen zum Einschränken der Größe des Baumsatzes finden Sie unter diesem Link

Angenommen, wir haben eine Wortfolge "ad" "ad" "boy" "big" "bad" "com" "come" "cold". Und K = 2. Wie Sie erwähnt haben "Partitionierung mit dem ersten Buchstaben", haben wir dann ("Anzeige", "Anzeige") ("Junge", "groß", "schlecht") ("com" "kommen" "kalt") " Partitionieren des größten Mehrwortsatzes mit dem nächsten Zeichen, bis Sie k Einzelwortsätze haben. " es wird partitioniert ("Junge", "groß", "schlecht") ("com" "kommt" "kalt"), die erste Partition ("Anzeige", "Anzeige") wird übersehen, während "Anzeige" tatsächlich die ist häufigstes Wort.

Vielleicht verstehe ich Ihren Standpunkt falsch. Können Sie bitte Ihren Prozess bezüglich der Partition detaillieren?

Ich glaube, dieses Problem kann durch einen O (n) -Algorithmus gelöst werden. Wir könnten die Sortierung im laufenden Betrieb durchführen. Mit anderen Worten, die Sortierung ist in diesem Fall ein Unterproblem des herkömmlichen Sortierproblems, da bei jedem Zugriff auf die Hash-Tabelle nur ein Zähler um eins erhöht wird. Zu Beginn wird die Liste sortiert, da alle Zähler Null sind. Während wir die Zähler in der Hash-Tabelle weiter inkrementieren, führen wir ein weiteres Array von Hash-Werten, die nach Häufigkeit geordnet sind, wie folgt. Jedes Mal, wenn wir einen Zähler erhöhen, überprüfen wir seinen Index im Rangarray und prüfen, ob seine Anzahl den Vorgänger in der Liste überschreitet. Wenn ja, tauschen wir diese beiden Elemente aus. Als solche erhalten wir eine Lösung, die höchstens O (n) ist, wobei n die Anzahl der Wörter im Originaltext ist.

Ich hatte auch damit zu kämpfen und ließ mich von @aly inspirieren. Anstatt danach zu sortieren, können wir einfach eine vorsortierte Liste von Wörtern ( List<Set<String>>) pflegen, und das Wort befindet sich in der Menge an Position X, wobei X die aktuelle Anzahl des Wortes ist. Im Allgemeinen funktioniert es folgendermaßen:

1. Speichern Sie es für jedes Wort als Teil der Karte seines Auftretens: Map<String, Integer> .
2. Entfernen Sie es dann basierend auf der Anzahl aus dem vorherigen Zählsatz und fügen Sie es dem neuen Zählsatz hinzu.

Der Nachteil dabei ist, dass die Liste möglicherweise groß ist - kann mithilfe von a optimiert werden TreeMap<Integer, Set<String>> -, aber dies erhöht den Overhead. Letztendlich können wir eine Mischung aus HashMap oder unserer eigenen Datenstruktur verwenden.

Der Code

public class WordFrequencyCounter {
    private static final int WORD_SEPARATOR_MAX = 32; // UNICODE 0000-001F: control chars
    Map<String, MutableCounter> counters = new HashMap<String, MutableCounter>();
    List<Set<String>> reverseCounters = new ArrayList<Set<String>>();

    private static class MutableCounter {
        int i = 1;
    }

    public List<String> countMostFrequentWords(String text, int max) {
        int lastPosition = 0;
        int length = text.length();
        for (int i = 0; i < length; i++) {
            char c = text.charAt(i);
            if (c <= WORD_SEPARATOR_MAX) {
                if (i != lastPosition) {
                    String word = text.substring(lastPosition, i);
                    MutableCounter counter = counters.get(word);
                    if (counter == null) {
                        counter = new MutableCounter();
                        counters.put(word, counter);
                    } else {
                        Set<String> strings = reverseCounters.get(counter.i);
                        strings.remove(word);
                        counter.i ++;
                    }
                    addToReverseLookup(counter.i, word);
                }
                lastPosition = i + 1;
            }
        }

        List<String> ret = new ArrayList<String>();
        int count = 0;
        for (int i = reverseCounters.size() - 1; i >= 0; i--) {
            Set<String> strings = reverseCounters.get(i);
            for (String s : strings) {
                ret.add(s);
                System.out.print(s + ":" + i);
                count++;
                if (count == max) break;
            }
            if (count == max) break;
        }
        return ret;
    }

    private void addToReverseLookup(int count, String word) {
        while (count >= reverseCounters.size()) {
            reverseCounters.add(new HashSet<String>());
        }
        Set<String> strings = reverseCounters.get(count);
        strings.add(word);
    }

}

Ich finde gerade die andere Lösung für dieses Problem heraus. Aber ich bin nicht sicher, ob es richtig ist. Lösung:

1. Verwenden Sie eine Hash-Tabelle, um die Häufigkeit aller Wörter T (n) = O (n) aufzuzeichnen.
2. Wählen Sie die ersten k Elemente der Hash-Tabelle aus und stellen Sie sie in einem Puffer wieder her (dessen Leerzeichen = k). T (n) = O (k)
3. Jedes Mal müssen wir zuerst das aktuelle min-Element des Puffers finden und das min-Element des Puffers nacheinander mit den (n - k) -Elementen der Hash-Tabelle vergleichen. Wenn das Element der Hash-Tabelle größer als dieses min-Element des Puffers ist, löschen Sie das min des aktuellen Puffers und fügen Sie das Element der Hash-Tabelle hinzu. Jedes Mal, wenn wir die minimale im Puffer finden, brauchen wir T (n) = O (k) und durchlaufen die gesamte Hash-Tabelle, brauchen wir T (n) = O (n - k). Die gesamte Zeitkomplexität für diesen Prozess ist also T (n) = O ((nk) * k).
4. Nach dem Durchlaufen der gesamten Hash-Tabelle befindet sich das Ergebnis in diesem Puffer.
5. Die gesamte Zeitkomplexität: T (n) = O (n) + O (k) + O (kn - k ^ 2) = O (kn + n - k ^ 2 + k). Da k im Allgemeinen wirklich kleiner als n ist. Für diese Lösung ist die zeitliche Komplexität also T (n) = O (kn) . Das ist eine lineare Zeit, wenn k wirklich klein ist. Ist es richtig? Ich bin mir wirklich nicht sicher.

Versuchen Sie, sich eine spezielle Datenstruktur auszudenken, um diese Art von Problemen anzugehen. In diesem Fall ist eine spezielle Baumart wie der Versuch, Zeichenfolgen auf bestimmte Weise zu speichern, sehr effizient. Oder eine zweite Möglichkeit, eine eigene Lösung wie das Zählen von Wörtern zu erstellen. Ich denke, diese TB Daten wären auf Englisch, dann haben wir im Allgemeinen ungefähr 600.000 Wörter, so dass es möglich sein wird, nur diese Wörter zu speichern und zu zählen, welche Zeichenfolgen wiederholt werden würden + diese Lösung benötigt Regex, um einige Sonderzeichen zu eliminieren. Die erste Lösung wird schneller sein, da bin ich mir ziemlich sicher.

http://en.wikipedia.org/wiki/Trie

Dies ist eine interessante Idee für die Suche und ich konnte dieses Papier im Zusammenhang mit Top-K https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pd finden f finden

Auch gibt es eine Implementierung es hier .

Einfachster Code, um das Auftreten des am häufigsten verwendeten Wortes zu ermitteln.

 function strOccurence(str){
    var arr = str.split(" ");
    var length = arr.length,temp = {},max; 
    while(length--){
    if(temp[arr[length]] == undefined && arr[length].trim().length > 0)
    {
        temp[arr[length]] = 1;
    }
    else if(arr[length].trim().length > 0)
    {
        temp[arr[length]] = temp[arr[length]] + 1;

    }
}
    console.log(temp);
    var max = [];
    for(i in temp)
    {
        max[temp[i]] = i;
    }
    console.log(max[max.length])
   //if you want second highest
   console.log(max[max.length - 2])
}

In diesen Situationen empfehle ich die Verwendung der in Java integrierten Funktionen. Da sind sie schon gut getestet und stabil. In diesem Problem finde ich die Wiederholungen der Wörter mithilfe der HashMap-Datenstruktur. Dann schiebe ich die Ergebnisse auf ein Array von Objekten. Ich sortiere das Objekt nach Arrays.sort () und drucke die obersten k Wörter und ihre Wiederholungen.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class TopKWordsTextFile {

    static class SortObject implements Comparable<SortObject>{

        private String key;
        private int value;

        public SortObject(String key, int value) {
            super();
            this.key = key;
            this.value = value;
        }

        @Override
        public int compareTo(SortObject o) {
            //descending order
            return o.value - this.value;
        }
    }


    public static void main(String[] args) {
        HashMap<String,Integer> hm = new HashMap<>();
        int k = 1;
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("words.in")));

            String line;
            while ((line = br.readLine()) != null) {
                // process the line.
                //System.out.println(line);
                String[] tokens = line.split(" ");
                for(int i=0; i<tokens.length; i++){
                    if(hm.containsKey(tokens[i])){
                        //If the key already exists
                        Integer prev = hm.get(tokens[i]);
                        hm.put(tokens[i],prev+1);
                    }else{
                        //If the key doesn't exist
                        hm.put(tokens[i],1);
                    }
                }
            }
            //Close the input
            br.close();
            //Print all words with their repetitions. You can use 3 for printing top 3 words.
            k = hm.size();
            // Get a set of the entries
            Set set = hm.entrySet();
            // Get an iterator
            Iterator i = set.iterator();
            int index = 0;
            // Display elements
            SortObject[] objects = new SortObject[hm.size()];
            while(i.hasNext()) {
                Map.Entry e = (Map.Entry)i.next();
                //System.out.print("Key: "+e.getKey() + ": ");
                //System.out.println(" Value: "+e.getValue());
                String tempS = (String) e.getKey();
                int tempI = (int) e.getValue();
                objects[index] = new SortObject(tempS,tempI);
                index++;
            }
            System.out.println();
            //Sort the array
            Arrays.sort(objects);
            //Print top k
            for(int j=0; j<k; j++){
                System.out.println(objects[j].key+":"+objects[j].value);
            }


        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

Weitere Informationen finden Sie unter https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java . Ich hoffe, es hilft.

**

C ++ 11 Implementierung des obigen Gedankens

** **.

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {

    unordered_map<int,int> map;
    for(int num : nums){
        map[num]++;
    }

    vector<int> res;
    // we use the priority queue, like the max-heap , we will keep (size-k) smallest elements in the queue
    // pair<first, second>: first is frequency,  second is number 
    priority_queue<pair<int,int>> pq; 
    for(auto it = map.begin(); it != map.end(); it++){
        pq.push(make_pair(it->second, it->first));

        // onece the size bigger than size-k, we will pop the value, which is the top k frequent element value 

        if(pq.size() > (int)map.size() - k){
            res.push_back(pq.top().second);
            pq.pop();
        }
    }
    return res;

}

};