D- 힙 우선 순위 대기열에서 가장 작은 하위를 찾는 방법을 구현하는 방법

Question

우선 순위 대기열 클래스에서 remove 메소드가 있습니다. 할당을 위해 처음부터 만들었습니다. 내가 만든 우선 순위 큐는 0에서 시작하는 배열로 배열에 보관됩니다. 배열 길이와 동일한 크기를 추적합니다. 제거 방법은 자격이 도우미 메서드를 사용

부모가 부모가 저장되는 배열의 위치를, 그리고 내가 그 작은 아이를 반환 찾고

public int findSmallest(int parent) 

. 순서는 잎이 아닌 각 노드에있는 자식 수입니다. 내 findSmallest의 코드는 :

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 가지 방법이 포함되어

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

은 현재 PriorityQueue 인 클래스의 완전한 구현은 내가 만든 경계 예외 밖으로 배열입니다. 문제는 바로 findSmallest 방법 인 경우

Answer 1

, 여기에 솔루션입니다 :

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 작은 아이가없는 경우. 이 코드는 향상시킬 수 있습니다. 이해하기 쉽기 때문에이 방법을 사용하도록하겠습니다. 작동하는지 알려주세요.