Dヒーププライオリティキューで最小の子を見つける方法を実装する方法

Question

プライオリティキュークラスにremoveメソッドがあります。割り当てのためにゼロから作成しました。私が作成したプライオリティキューは、インデックスが0から始まる配列に保持されます。配列の長さと等しいサイズを追跡します。

public int findSmallest(int parent) 

親が親がに格納されていることを、アレイ内の位置である、と私はその最小の子を返すように探しています：removeメソッドは、題しヘルパーメソッドを使用しています。順序は、単に葉ではない各ノードの子ノードの数です。私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; 
} 

それが現在私が作成した優先度つきキュークラスの境界例外 完全な実装のうち配列です：

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"); 
    } 
} 

主は、私は自分のコードをテストしてい3種類の方法が含まれます。

Answer 1

あなたの問題は、単にfindSmallest方法であれば、ここでの解決策は次のとおりです。

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; 

} 

それは-1を返します小さい子がない場合。このコードは改善することができます、私はそれが理解しやすいと思うので、私はそれをこのようにしました。それが動作するかどうか私に教えてください。