在 Java 中使用泛型实现堆

Question

我想实现一个基于数组的堆。但是，这个 Heap 应该可以使用仅实现 Comparable 接口的元素的 Array 或使用附加的 Comparator 调用（因此，如果没有给出 Comparator，则假定每个元素都可以相互比较）。然后我想检查它的有效性。它不起作用，因为无法调用 extends Comparable 的 heapCondition。

public class Heap <T>{
Object[] tree;
Comparator<T> comparator;

public <T extends Comparable<T>> Heap(T[] tree){
    this.tree = tree;
}

public Heap(T[] tree, Comparator<T> comparator){
    this.tree = tree;
    this.comparator = comparator;
}

/**
 * defines the heapCondition default is set so the Heap is a minHeap (parent is smaller than their children)
 * @param parent parent node
 * @param child child node
 */
public <T extends Comparable<T>> boolean heapCondition(T parent, T child){
    return parent.compareTo(child) < 0;
}

public boolean heapCondition(T parent, T child){
    if(comparator == null){
        // go into the heap condition where to Comparable is assumed
        heapCondition(parent,child);
    }
    return comparator.compare(parent,child) < 0;
}


/**
 * @return boolean whether or not the current tree fulfills the Heap condition
 *
 */
private boolean valid(){
    for(int i = 0; 2*i+2 < tree.length; i++){
        // returns false if the condition is not met for one of the children
        return !(!heapCondition((T) tree[i], (T) tree[2*i+1]) || !heapCondition((T) tree[i],(T) tree[2*i+2]));
    }
    return true;
}
}

Answer 1

在您的实现中，Heap <T> 和 public <T extends Comparable<T>> boolean heapCondition 不是相同的 T。通用方法根据 class 定义创建其他 T 和 shadows T。这就是为什么你的 public boolean heapCondition 不能调用 public <T ...> boolean heapCondition.

实际上，在 Comparator == null 和 T 为任何 class 的情况下，您不能要求 T 为 Comparable。 java.util.TreeMap 实现了类似的东西。它在 Comparator == null 时使用 compareTo。但是这个逻辑是通过使用运行时转换并在对象不是 Comparable 时抛出 ClassCastException 来完成的。这是 java.util.TreeMap

的 JavaDoc

     /**
     * Constructs a new, empty tree map, using the natural ordering of its
     * keys.  All keys inserted into the map must implement the {@link
     * Comparable} interface.  Furthermore, all such keys must be
     * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
     * a {@code ClassCastException} for any keys {@code k1} and
     * {@code k2} in the map.  If the user attempts to put a key into the
     * map that violates this constraint (for example, the user attempts to
     * put a string key into a map whose keys are integers), the
     * {@code put(Object key, Object value)} call will throw a
     * {@code ClassCastException}.
     */
    public TreeMap() {
        comparator = null;
    }

这是 getEntry 将元素转换为 Comparable 的实现：

    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    ...

解决方案

您需要删除除 Heap <T> 定义之外的所有泛型。此外，当您的 comparator == null 时，您不会返回结果，从而进行无限递归。在您的 valid 方法中，您总是在第一次迭代后返回。

这是您的堆的样子。

class Heap<T> {
    T[] tree;
    Comparator<? super T> comparator;

    public Heap(T[] tree) {
        this.tree = tree;
        this.comparator = null;
    }

    public Heap(T[] tree, Comparator<? super T> comparator) {
        this.tree = tree;
        this.comparator = comparator;
    }

    /**
     * defines the heapCondition default is set so the Heap is a minHeap (parent is smaller than their children)
     *
     * @param parent parent node
     * @param child  child node
     */
    public boolean heapConditionComparable(T parent, T child) {
        @SuppressWarnings("unchecked")
        Comparable<? super T> comparableParent = (Comparable<? super T>) parent;
        return comparableParent.compareTo(child) < 0;
    }

    public boolean heapCondition(T parent, T child) {
        if (comparator == null) {
            // go into the heap condition where to Comparable is assumed
            return heapConditionComparable(parent, child);
        }
        return comparator.compare(parent, child) < 0;
    }


    /**
     * @return boolean whether or not the current tree fulfills the Heap condition
     */
    boolean valid() {
        for (int i = 0; i < (tree.length - 2) / 2; ++i) {
            // returns false if the condition is not met for one of the children
            if (!(!heapCondition(tree[i], tree[2 * i + 1]) || !heapCondition(tree[i], tree[2 * i + 2]))) {
                return false;
            }
        }
        return true;
    }
}

Answer 2

您可以查看处理类似问题的 TreeMap，但我觉得它的方法不是很优雅。我会使用静态工厂方法来更好地控制类型，并为自然排序分配一个默认比较器。这样你就不用担心调用哪个比较方法了：

public static <T> Heap<T> create(T[] tree, Comparator<T> comparator) {
    return new Heap<>(tree, comparator);
}

public static <T extends Comparable<T>> Heap<T> create(T[] tree) {
    return new Heap<>(tree, Comparator.naturalOrder());
}

private Heap(T[] tree, Comparator<T> comparator) {
    this.tree = tree;
    this.comparator = comparator;
}

public boolean heapCondition(T parent, T child) {
    return comparator.compare(parent, child) < 0;
}

在 Java 中使用泛型实现堆

Implement Heap with generics in Java

java

arrays

generics

heap

comparable

解决方案