如何在Java中实现heap类的堆和克隆方法

Question

我正在编写一个类，用clone和equal方法实现堆。我为每种方法创建了特定的测试用例。

预期：

heap1: 6
heap2: 6
equals? true
heap1: 5
heap2: 6
equals? false

实际：

heap1: 6
heap2: 6
equals? true
heap1: 5
heap2: 5
equals? true

我的尝试

public static void main(String[] args) {
String[] strings = {"red", "green", "purple", "orange", "yellow", "cyan"};
try{
Heap<String> heap1 = new Heap<>(strings);  
Heap<String> heap2 = (Heap<String>)(heap1.clone());

System.out.println("heap1: " + heap1.getSize());
System.out.println("heap2: " + heap2.getSize());
System.out.println("equals? " + heap1.equals(heap2));

heap1.remove();

System.out.println("heap1: " + heap1.getSize());
System.out.println("heap2: " + heap2.getSize());

System.out.println("equals? " + heap1.equals(heap2));
}
catch (Exception e){
System.out.print(e.getMessage());
}
}


static class Heap<E> implements Cloneable {
private java.util.ArrayList<E> list = new java.util.ArrayList<>();
private java.util.Comparator<? super E> c;

/** Create a default heap using a natural order for comparison */
public Heap() {
this.c = (e1, e2) -> ((Comparable<E>)e1).compareTo(e2);
}

/** Create a heap with a specified comparator */
public Heap(java.util.Comparator<E> c) {
this.c = c;
}

/** Create a heap from an array of objects */
public Heap(E[] objects) {
this.c = (e1, e2) -> ((Comparable<E>)e1).compareTo(e2);
for (int i = 0; i < objects.length; i++)
add(objects[i]);
}

/** Add a new object into the heap */
public void add(E newObject) {
list.add(newObject); // Append to the heap
int currentIndex = list.size() - 1; // The index of the last node

while (currentIndex > 0) {
int parentIndex = (currentIndex - 1) / 2;
// Swap if the current object is greater than its parent
if (c.compare(list.get(currentIndex),
list.get(parentIndex)) > 0) {
E temp = list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex, temp);
}
else
break; // the tree is a heap now

currentIndex = parentIndex;
}
}

/** Remove the root from the heap */
public E remove() {
if (list.size() == 0) return null;

E removedObject = list.get(0);
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);

int currentIndex = 0;
while (currentIndex < list.size()) {
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;

// Find the maximum between two children
if (leftChildIndex >= list.size()) break; // The tree is a heap
int maxIndex = leftChildIndex;
if (rightChildIndex < list.size()) {
if (c.compare(list.get(maxIndex),
list.get(rightChildIndex)) < 0) {
maxIndex = rightChildIndex;
}
}

// Swap if the current node is less than the maximum
if (c.compare(list.get(currentIndex), 
list.get(maxIndex)) < 0) {
E temp = list.get(maxIndex);
list.set(maxIndex, list.get(currentIndex));
list.set(currentIndex, temp);
currentIndex = maxIndex;
}
else
break; // The tree is a heap
}

return removedObject;
}

/** Get the number of nodes in the tree */
public int getSize() {
return list.size();
}

/** Return true if heap is empty */
public boolean isEmpty() {
return list.size() == 0;
}

// BEGIN REVEL SUBMISSION
@Override /** Override the proctected clone method defined in
the Object class, and stregthen its accessibility */
public Object clone() throws CloneNotSupportedException {
return super.clone();
}

@Override /** Override the equals method in the Object cl */
public boolean equals(Object other) {
if (list.size() != ((Heap<E>) (other)).getSize())
return false;

for (int i = 0; i < list.size(); i++) {
if (list.get(i) != ((Heap<E>) (other)).list.get(i))
return false;
}
return true;
}
// END REVEL SUBMISSION
}

如何从该方法中具体返回堆？

@Override /** Override the protected clone method defined in
the Object class, and strengthen its accessibility */
public Object clone() throws CloneNotSupportedException {
return list.clone();
}

问题可能来自

heap1.remove();

Answer 1

问题是heap1和heap2具有相同的内部列表。super.clone只克隆指定的对象，但不克隆其属性。

解决方案：

Heap<E> heap = new Heap();
heap.list = new ArrayList(list);
return heap;

正如@Slaw所提到的，您可能还想创建一个复制构造函数。

完全克隆具有所有属性及其属性的对象的过程称为深度克隆。