Komplexität von Operationen auf einem Heap fester Größe

Question

Ich studiere für eine anstehende Prüfung und stieß auf ein Problem, bei dem ich eine Top 10 der höchsten Ganzzahlen aus einem eingehenden, unendlichen Zahlenstrom aufbauen und pflegen musste. Ich dachte, ich könnte einen Min-Heap von fester Größe 10 verwenden, und wenn ich eine neue Nummer erhalte, könnte ich einfach überprüfen, ob das Minimum niedriger als die neue eingehende Nummer ist. Wenn ja, müsste ich den Heap aktualisieren indem ich die Wurzel sequentiell entwerfe, bis ich einen höheren Wert erhalte, und dann die neue Zahl einfüge, zusammen mit den vorher herausgefallenen Wurzeln (minus der ersten, um die feste Größe von 10 beizubehalten). Jetzt, wo ich diesen Heap habe, kann ich leicht die Top 10 erreichen, indem ich jeden Knoten im Heap platziere und drucke.

Ich habe eine Methode in Java programmiert, die mit einer PriorityQueue das erreichen würde, was ich sage.

public void addNumber(int number){ 
    if(pq.size() < 10){ 
     pq.offer(number); 
    } 
    else if(pq.peek() < number){ 
     List<Integer> topNumbers = new LinkedList<Integer>(); 
     while(!pq.isEmpty() && pq.peek() < number){ 
      topNumbers.add(pq.poll()); 
     } 
     pq.offer(number); 
     for(int i = 1; i < topNumbers.size(); i++){ 
      pq.offer(topNumbers.get(i)); 
     } 
    } 
} 

public void printTop10(){ 
    List<Integer> topNumbers = new LinkedList<Integer>(); 
    while(!pq.isEmpty()){ 
     topNumbers.add(pq.poll()); 
    } 

    for(int i = 0; i < topNumbers.size(); i++){ 
     Node thisOne = topNumbers.get(topNumbers.size() - 1 - i); 
     System.out.println(thisOne); 
     pq.offer(thisOne); 
    } 
} 

Nach meinen Tests funktioniert dieser Code und funktioniert wie erwartet. Nun, hier kommt meine Frage. Was wäre die Komplexität für diese beiden Operationen? Wir haben eine PriorityQueue, daher sind die Operationen insert und extract-min logarithmisch. Aber in diesem Fall ist die Größe des Heaps, "n", höchstens 10. Bedeutet das, dass die Komplexität dann O (log 10) ist, was im Wesentlichen konstante O (1) Zeit ist?

Answer 1

Ja; der Logarithmus einer Konstanten ist ebenfalls konstant.

Oft werden solche Algorithmen analysiert, indem ihre Laufzeit als eine Funktion mehrerer Variablen beschrieben wird. Zum Beispiel könnten wir sagen, dass Ihr Algorithmus die obersten k aus n Zahlen in O (n log k) Zeit und O (k) Raum extrahiert. Wenn der Wert von k bekannt ist, können wir diese Tatsache auch verwenden, um unsere Analyse zu vereinfachen.