cómo determinar si el elemento kth más grande del montón es mayor que x

Question

Considere un montón binario que contiene n números (la raíz almacena el mayor número). Le dan un número entero positivo k < n y un número x. Debe determinar si el k-ésimo elemento más grande del montón es mayor que xo no. Su algoritmo debe tomar el tiempo O (k). Puede utilizar O (k) almacenamiento extra

Answer 1

Dfs simples pueden hacerlo, tenemos un contador configurado en cero. Comience desde la raíz y en cada iteración verifique el valor del nodo si es mayor que x, luego aumente el contador y ejecute el algoritmo para los nodos secundarios. Cuando el contador es mayor o igual a k, el algoritmo estará terminado, también, si no hay un nodo para verificar, el algoritmo devuelve falso. El código es simple. El tiempo de ejecución es O (k) porque como máximo comprobarás k nodo y cada iteración es O (1).

El pseudo-código tiene el siguiente aspecto.

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; 

si node.value < x todos los valores de los niños son más pequeños que X y no hay necesidad de comprobar.

Como @Eric Mickelsen mencionó en los comentarios el peor caso, el tiempo de ejecución es exactamente 2k-1 (k> 0) de la siguiente manera.

El número de nodos visitados con valores mayores que x será como máximo de k. Cada nodo visitado con un valor menor que x debe ser un elemento secundario de un nodo visitado con un valor mayor que x. Sin embargo, dado que cada nodo visitado, excepto que la raíz debe tener un padre con un valor mayor que x, , el número de nodos de valor menor que x visitado debe ser como máximo ((k-1) * 2) - (k-1) = k-1, ya que k-1 de los (k-1) * 2 niños tienen valores mayor que x. Esto significa que visitamos k nodos mayores que xy k-1 menor que x, que es 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)); 
} 

}