2017-10-11 5 views
0

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

부모가 부모가 저장되는 배열의 위치를, 그리고 내가 그 작은 아이를 반환 찾고
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 방법 인 경우

+0

전체 구현을 게시 할 수 있습니까? – davidbuzatto

+0

업데이트 됨, 고맙습니다. –

+0

살펴 보겠습니다. 기다려주십시오. – davidbuzatto

답변

0

, 여기에 솔루션입니다 :

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

+0

그것은 실제로 작동하지 않고 실제로 생성되지 않았으며 null 값을 보유한 자식을 찾고 있기 때문에 findSmallest (i