힙 반복자 java

힙 트리에이 코드가 있으며 반복기가 붙어 있습니다.
순서대로, 선주 주문 및 사후 주문 반복기가 필요하지만 어떻게해야하는지 잘 모릅니다.힙 반복자 java

누군가 아이디어 나 예제가있는 경우 도움을 받으십시오.

class Numbers implements Comparable<Numbers> { 
     private int value; 

     public Numbers(int value) { 
      this.value = value; 
     } 

     public String toString() { 
      return Integer.toString(value); 
     } 

     public int getValue() { 
      return this.value; 

    } 

    public int compareTo(Numbers o) { 
     int tmp = o.getValue(); 
     if (value > tmp) 
     return 1; 
     if (value < tmp) 
     return -1; 
     return 0; 
    } 
} 

class BinaryHeapIsFull extends Exception { 
    BinaryHeapIsFull() { 
     super("There is no more place in the heap!"); 
    } 
} 

public class BinaryHeap<E extends Comparable> { 
    E[] elements; 
    int count; 

    public BinaryHeap(int maxSize) { 
     elements = (E[]) new Comparable[maxSize];          
     this.count = 0; 
    } 

    public void enqueue(E elem) throws BinaryHeapIsFull { 
     if (count == elements.length) 
     throw new BinaryHeapIsFull(); 

     int i = count++; 
     while (i > 0 && elements[(i - 1)/2].compareTo(elem) == 1) { 
     elements[i] = elements[(i - 1)/2]; 
     i = (i - 1)/2; 
     } 
     elements[i] = elem; 
    } 

    public E findMin() { 
     return elements[0]; 
    } 

    public E dequeueMin() { 
     if (count == 0) 
     return null; 
     E result = elements[0]; 

     E last = elements[--count]; 

     int i = 0; 
     while (2 * i + 1 <= count) { 
     int child = 2 * i + 1; 
     if (child < count 
       && elements[child + 1].compareTo(elements[child]) == -1) 
      child++; 
     if (last.compareTo(elements[child]) == -1 
       || last.compareTo(elements[child]) == 0) 
      break; 
     elements[i] = elements[child]; 
     i = child; 
     } 
     elements[i] = last; 
     return result; 
    } 

    public String toString() { 
     String print = ""; 
     for (int i = 0; i < count; i++) 
     print += elements[i].toString() + " "; 
     return print; 
    } 

    public void sort() { 
     int a = count; 
     for (int i = 0; i < a; i++) { 
     System.out.print(findMin() + " "); 
     dequeueMin(); 
     } 
    } 

    public static void main(String[] args) throws BinaryHeapIsFull { 
     BinaryHeap<Numbers> b = new BinaryHeap<Numbers>(10); 
     b.enqueue(new Numbers(6)); 
     System.out.println(b.toString()); 
     b.enqueue(new Numbers(3)); 
     System.out.println(b.toString()); 
     b.enqueue(new Numbers(4)); 
     System.out.println(b.toString()); 
     b.enqueue(new Numbers(1)); 
     System.out.println(b.toString()); 
     b.enqueue(new Numbers(5)); 
     System.out.println(b.toString()); 
     b.enqueue(new Numbers(0)); 
     System.out.println(b.toString()); 
     b.enqueue(new Numbers(2)); 
     System.out.println(b.toString()); 
     b.dequeueMin(); 
     System.out.println(b.toString()); 
     b.dequeueMin(); 
     System.out.println(b.toString()); 
     System.out.println(b.findMin()); 
     b.sort(); 

    } 
}

출처

2011-08-15 Vlatko

이 숙제가 있습니까? –

이 반복자가하는 작업의 차이점에 대해 알고 있습니까? 그리고 요소 N, N * 2와 N * 2 + 1 사이의 관계를 이해합니까? – parsifal

Iterator 인터페이스를 구현하는 각각의 경우에 하나씩 세 가지 클래스로 시작하겠습니다. 이러한 반복자에 바이너리 힙 인스턴스를 지정하고 해당 작업을 수행하게하십시오.

public class BinaryHeapPreOrderIterator implements Iterator { 
    // constructor and methods for Iterator here. 
}

출처

2011-08-15 10:45:08 duffymo

힙 반복자 java

답변

관련 문제