come determinare se il kesimo elemento più grande dell'heap è maggiore di x

Question

Si consideri un heap binario contenente n numeri (la radice memorizza il numero più grande). Viene fornito un intero positivo k < n e un numero x. È necessario determinare se il kesimo elemento più grande dell'heap è maggiore di x o meno. L'algoritmo deve richiedere O (k) di tempo. È possibile utilizzare O (k) memoria aggiuntiva

Answer 1

Semplice dfs può farlo, abbiamo un contatore impostato su zero. Partendo dalla radice e in ogni iterazione, verificare se il valore del nodo è maggiore di x, quindi aumentare il contatore ed eseguire l'algoritmo per i nodi figlio. Quando il contatore è più grande o uguale a k l'algoritmo sarà terminato, anche se non ci sono nodi da controllare, l'algoritmo restituisce false. Il codice è semplice. Il tempo di esecuzione è O (k) perché al massimo si controlla il nodo k e ogni iterazione è O (1).

Lo pseudo-codice si presenta come segue.

void CheckNode(Node node,int k, int x, ref int counter) 
    { 
     if (node.value > x) 
     { 
      counter++; 
      if (counter >= k) 
       return; 

      CheckNode(node.Left, k, x, ref counter); 
      CheckNode(node.Right,k, x, ref counter); 
     } 
    } 

usarlo:

 counter = 0; 
     CheckNode(root,index,val,counter); 
     if (counter >= index) 
      return true; 
     return false; 

se node.value < x tutti i valori di bambini sono più piccoli di x e non c'è bisogno di controllare.

Come @Eric Mickelsen menzionato nei commenti nel peggiore dei casi il tempo di esecuzione è esattamente 2k-1 (k> 0) come segue.

Il numero di nodi visitato con valori maggiori di x sarà al massimo k. Ogni nodo visitato con valore inferiore a x deve essere figlio di un nodo visitato con valore maggiore di x. Tuttavia, poiché ogni nodo visitato tranne la radice deve avere un genitore con valore maggiore di x, il numero di nodi di valore inferiore a x visitato deve essere al massimo ((k-1) * 2) - (k-1) = k-1, poiché k-1 dei bambini (k-1) * 2 ha valori maggiori di x. Ciò significa che visitiamo k nodi maggiori di x e k-1 meno di x, che è 2k-1.

Answer 2

public class KSmallest2 { 

private MinPQ<Integer> minHeap; 
private int x; 
private int k; 
private int count = 0; 

public KSmallest2(String filename, int x, int k) { 
    this.x = x; 
    this.k = k; 
    minHeap = new MinPQ<>(); 
    try { 
     Scanner in = new Scanner(new File(filename)); 
     while (in.hasNext()) { 
      minHeap.insert(in.nextInt()); 
     } 
    } catch (FileNotFoundException e) { 
     e.printStackTrace(); 
    } 
} 

public boolean check(int index) { 

    if (index > minHeap.size()) { 
     return false; 
    } 

    if (minHeap.getByIndex(index) < x) { 
     count++; 
     if (count >= k) { 
      return true; 
     } 

     return check(2 * index) || 
       check(2 * index + 1); 
    } 

    return false; 
} 



public static void main(String[] args) { 
    KSmallest2 ks = new KSmallest2("src/main/resources/minheap.txt", 18, 5); 
    System.out.println(ks.minHeap); 

    System.out.println(ks.check(1)); 
} 

}