Я реализовал интерфейс Priority Queue для создания кучи. Можете ли вы сказать мне, как реализовать итератор на вершине этого? укажите мне на соответствующий учебник, я новичок в 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);
}
// Класс BinaryHeap
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;
}