如何在java中使用迭代器？

Question

我已经实现了优先队列接口来制作堆。你能告诉我如何在上面实现一个迭代器吗？点我一些适当的教程，我是新来的Java和在这里很短的截止日期。 其实我需要一种方法来根据Object.id从堆中找到和修改一个对象。我不在乎它是否是O（n）。

public interface PriorityQueue { 

    /** 
    * The Position interface represents a type that can 
    * be used for the decreaseKey operation. 
    */ 
    public interface Position { 

     /** 
     * Returns the value stored at this position. 
     * @return the value stored at this position. 
     */ 
     Comparable getValue(); 
    } 

    Position insert(Comparable x); 

    Comparable findMin(); 

    Comparable deleteMin(); 

    boolean isEmpty(); 

    int size(); 

    void decreaseKey(Position p, Comparable newVal); 
} 

//二叉堆类

public class OpenList implements PriorityQueue { 

    public OpenList() { 
     currentSize = 0; 
     array = new Comparable[DEFAULT_CAPACITY + 1]; 
    } 

    public OpenList(int size) { 
     currentSize = 0; 
     array = new Comparable[DEFAULT_CAPACITY + 1]; 
     justtocheck = new int[size]; 
    } 

    public OpenList(Comparable[] items) { 
     currentSize = items.length; 
     array = new Comparable[items.length + 1]; 

     for (int i = 0; i < items.length; i++) { 
      array[i + 1] = items[i]; 
     } 
     buildHeap(); 
    } 

    public int check(Comparable item) { 
     for (int i = 0; i < array.length; i++) { 
      if (array[1] == item) { 
       return 1; 
      } 
     } 
     return array.length; 
    } 

    public PriorityQueue.Position insert(Comparable x) { 
     if (currentSize + 1 == array.length) { 
      doubleArray(); 
     } 

     // Percolate up 
     int hole = ++currentSize; 
     array[ 0] = x; 

     for (; x.compareTo(array[hole/2]) < 0; hole /= 2) { 
      array[hole] = array[hole/2]; 
     } 
     array[hole] = x; 

     return null; 
    } 

    public void decreaseKey(PriorityQueue.Position p, Comparable newVal) { 
     throw new UnsupportedOperationException(
      "Cannot use decreaseKey for binary heap"); 
    } 

    public Comparable findMin() { 
     if (isEmpty()) { 
      throw new UnderflowException("Empty binary heap"); 
     } 
     return array[ 1]; 
    } 

    public Comparable deleteMin() { 
     Comparable minItem = findMin(); 
     array[ 1] = array[currentSize--]; 
     percolateDown(1); 

     return minItem; 
    } 

    private void buildHeap() { 
     for (int i = currentSize/2; i > 0; i--) { 
      percolateDown(i); 
     } 
    } 

    public boolean isEmpty() { 
     return currentSize == 0; 
    } 

    public int size() { 
     return currentSize; 
    } 

    public void makeEmpty() { 
     currentSize = 0; 
    } 
    private static final int DEFAULT_CAPACITY = 100; 
    private int currentSize;  // Number of elements in heap 
    private Comparable[] array; // The heap array 
    public int[] justtocheck; 

    private void percolateDown(int hole) { 
     int child; 
     Comparable tmp = array[hole]; 

     for (; hole * 2 <= currentSize; hole = child) { 
      child = hole * 2; 
      if (child != currentSize && 
       array[child + 1].compareTo(array[child]) < 0) { 
       child++; 
      } 
      if (array[child].compareTo(tmp) < 0) { 
       array[hole] = array[child]; 
      } else { 
       break; 
      } 
     } 
     array[hole] = tmp; 
    } 

    private void doubleArray() { 
     Comparable[] newArray; 

     newArray = new Comparable[array.length * 2]; 
     for (int i = 0; i < array.length; i++) { 
      newArray[i] = array[i]; 
     } 
     array = newArray; 

} 

Answer 1

您可能会看到java.util.PriorityQueue。如果您匆忙，Arrays.sort()就足够了。一旦排序，Arrays.binarySearch()成为可能。

Answer 2

你的底层数据结构是数组，这是难以编写Java风格的迭代器。您可以尝试创建一个实现java.util.Iterator的容器类，该容器包含对Comparable元素及其当前数组索引的引用。移动容器时，您需要手动更新索引。