Comment implémenter une méthode pour rechercher le plus petit enfant dans une file d'attente prioritaire de segment D

Question

J'ai une méthode remove dans une classe Priority Queue que j'ai créée de toutes pièces pour une affectation. La file d'attente de priorité que j'ai créée est maintenue dans un tableau, l'index commençant à 0. Je garde la trace de la taille qui est égale à la longueur des tableaux. La méthode remove utilise une méthode d'aide intitulée:

public int findSmallest(int parent) 

où parent est la position dans le tableau que le parent est stocké à, et je cherche à retourner son plus petit enfant. L'ordre est simplement le nombre d'enfants de chaque nœud qui n'est pas une feuille. Le code pour mon findSmallest:

public int findSmallest(int parent) { 
    int child = parent * order + 1; 
    int smallest = child; 
    for (int i = child; i < order + child; ++i) { 
     if (size >= i) { 
      return child; 
     } 
     if (queue[i].priority <= queue[smallest].priority) { 
      smallest = child; 
     } 
    } 
    return child; 
} 

Il est actuellement un tableau hors limites exception mise en œuvre complète de PriorityQueue Classe I créé:

import java.util.*; 

public class PriorityQueue { 

    private class Item { 
     private int priority; 
     private Object data; 

     private Item(int p, Object d) { 
      priority = p; 
      data = d; 
     } 
    } 

    private Item queue[]; 
    private int order; 
    private int size; 

    public PriorityQueue(int ord, int s) { 
     queue = new Item[s]; 
     order = ord; 
     size = 0; 
    } 

    public int getPriority() { 
     if (size > 0) { 
      return queue[0].priority; 
     } 

     // -55 signifies that the queue is empty 

     return -55; 
    } 

    public Object getData() { 
     if (size > 0) { 
      return queue[0].priority; 
     } 
     return null; 
    } 

    public void remove() { 

     if (empty() == true) { 
      System.out.println("Queue is empty, there is nothing to remove."); 
      return; 
     } 

     Item x = queue[size - 1]; 
     size--; 
     int child = 1; 
     int parent = 0; 

     while (child <= size) { 
      child = findSmallest(parent); 
      for (int i = order * parent + 1; i < child + order; i++) { 
       if (child < size && queue[i].priority < queue[child].priority) 
        child = i; 
      } 
      if (x.priority < queue[child].priority) 
       break; 
      else { 
       parent = child; 
       queue[(child - 1)/order] = queue[child]; 
       child = order * child + 1; 
      } 
     } 
     queue[(child - 1)/order] = x; 
    } 

    public int findSmallest(int parent) { 
     int child = parent * order + 1; 
     int smallest = child; 
     for (int i = child; i < order + child; ++i) { 
      if (size >= i) { 
       return child; 
      } 
      if (queue[i].priority <= queue[smallest].priority) { 
       smallest = child; 
      } 
     } 
     return child; 
    } 

    public int getSize() { 
     return size; 
    } 

    public boolean full() { 
     return size == queue.length; 
    } 

    public boolean empty() { 
     if (size > 0) { 
      return false; 
     } 
     return true; 
    } 

    public void insert(int p, Object d) { 
     // 1. Create a new Item and add it to queue[size] 
      // Somewhere store new node created as TEMP 
     // 2. while loop 
     // 3. check if node has parent 
      // 4. if it does --> check if parent.priority > child.priority 
       // 5. if yes, swap 

     if (full() == true) { 
      System.out.println("Queue is full, cannot add new node."); 
      return; 
     } 

     queue[size] = new Item(p, d); 
     sort(); 
     size++; 

    } 

    // Sort() swaps new child node with parents if child.priority < parent.priority 

    public void sort() { 

     int child = size; 
     Item temp = queue[child]; 
     while (child > 0 && queue[child].priority < queue[(child-1)/(order)].priority) { 
      queue[child] = queue[(child-1)/order]; 
      queue[(child-1)/order] = temp; 
      child = ((child - 1)/order); 
     } 
     queue[child] = temp; 
    } 



    public static void main(String[] args) { 
      PriorityQueue p1 = new PriorityQueue(5, 100); 
      PriorityQueue p2 = new PriorityQueue(6, 100); 
      PriorityQueue p3 = new PriorityQueue(7, 100); 

      int p = -1; //pointless initialization to keep the compiler happy 
      p1.insert(0, new Integer(0)); 
      System.out.println("First insert"); 

      for (int i = 1; i < 100; i++) 
       p1.insert(i, new Integer(i)); 

      for (int i = 0; i < 100; i++) 
       p2.insert(i, new Integer(i)); 

      for (int i = 0; i < 100; i++) 
       p3.insert(i, new Integer(i)); 

      System.out.println("First insert tests"); 

      System.out.print(p1.getPriority()+","); 
      while (!p1.empty()) { 
       p = p1.getPriority(); 
       Object d = p1.getData(); 
       p1.remove(); 
      } 
      System.out.println(p); 

      System.out.print(p2.getPriority()+","); 

      while (!p2.empty()) { 
       p = p2.getPriority(); 
       Object d = p2.getData(); 
       p2.remove(); 
      } 
      System.out.println(p); 

      System.out.print(p3.getPriority()+","); 

      while (!p3.empty()) { 
       p = p3.getPriority(); 
       Object d = p3.getData(); 
       p3.remove(); 
      } 
      System.out.println(p); 
      System.out.println("First Remove Test"); 

      for (int i = 100; i > 0 ; i--) 
       p1.insert(i, new Integer(i)); 

      for (int i = 100; i > 0 ; i--) 
       p2.insert(i, new Integer(i)); 

      for (int i = 100; i > 0 ; i--) 
       p3.insert(i, new Integer(i)); 

      System.out.println("Second insert tests"); 

      System.out.print(p1.getPriority()+","); 
      while (!p1.empty()) { 
       p = p1.getPriority(); 
       Object d = p1.getData(); 
       p1.remove(); 
      } 
      System.out.println(p); 

      System.out.print(p2.getPriority()+","); 

      while (!p2.empty()) { 
       p = p2.getPriority(); 
       Object d = p2.getData(); 
       p2.remove(); 
      } 
      System.out.println(p); 

      System.out.print(p3.getPriority()+","); 

      while (!p3.empty()) { 
       p = p3.getPriority(); 
       Object d = p3.getData(); 
       p3.remove(); 
      } 
      System.out.println(p); 
      System.out.println("Second Remove Test"); 

      Random r1 = new Random(1000); 
      while (!p3.full()) { 
       p = r1.nextInt(200); 
       System.out.print(p+","); 
       p3.insert(p, new Integer(p)); 
      } 
      System.out.println(); 

      while (!p3.empty()) { 
       System.out.print(p3.getPriority()+","); 
       Object d = p3.getData(); 
       p3.remove(); 
      } 
      System.out.println(); 
      System.out.println("Third Remove Test"); 
    } 
} 

principal comprend 3 façons différentes que je teste mon code.

Answer 1

Si votre problème est juste la méthode findSmallest, voici la solution:

public int findSmallest(int parent) { 

    int smallestChild = -1; 

    int firstChild = parent * order + 1; 
    int lastChild = parent * order + order; 

    int currentSmallestChild = firstChild; 

    for (int i = firstChild + 1; i <= lastChild; i++) { 
     if (i > size || queue[i] == null) { 
      break; 
     } 
     if (queue[currentSmallestChild].priority > queue[i].priority) { 
      currentSmallestChild = i; 
      smallestChild = i; 
     } 
    } 

    return smallestChild; 

} 

Il retourne -1 s'il n'y a pas un plus petit enfant. Ce code peut être amélioré, je le laisse faire car je pense que c'est plus facile à comprendre. Laissez-moi savoir si cela fonctionne.