我正在尝试编写一个通用堆类。
import java.util.ArrayList;
public class heap<T extends Comparable<T>>
{
private ArrayList<T> h;
private int size;
public heap()
{
h = new ArrayList<T>();
h.add(null);
size = 0;
}
public T getMin()
{
return h.get(1);
}
public T popMin()
{
T tmp = getMin();
h.set(1, h.get(size));
size--;
sift(1);
return tmp;
}
public void insert(T key)
{
h.add(key);
percolate(++size);
}
public int getSize()
{
return this.size;
}
private int getLeftSon(int i)
{
return (i<<1<=size)? i<<1 : 0;
}
private int getRightSon(int i)
{
return ((i<<1)+1<=size)? (i<<1)+1 : 0;
}
private int getFather(int i)
{
return ((i>>1)!=0)? i>>1 : 0;
}
private void swap(int i, int j)
{
T tmp = h.get(i);
h.set(i, h.get(j));
h.set(j, tmp);
}
private void sift(int i)
{
int son;
do {
son = 0;
if (getLeftSon(i) != 0)
{
son = getLeftSon(i);
if (getRightSon(i) != 0 && h.get(getRightSon(i)).compareTo(h.get(getLeftSon(i))) > 0)
son = getRightSon(i);
if (h.get(son).compareTo(h.get(i)) <= 0)
son = 0;
}
if (son!=0) {
swap(i, son);
i = son;
}
} while (son!=0);
}
private void percolate(int i)
{
T key = h.get(i);
while ((i > 1) && (key.compareTo(h.get(getFather(i))) > 0))
{
h.set(i, h.get(getFather(i)));
i = getFather(i);
}
h.set(i, key);
}
}
一切顺利。它就像一个魅力。除了一件事:如果我使用 Integers,我无法从 Integer 中“访问”compareTo
方法。这意味着我无法覆盖它的行为。我将始终以这种方式拥有最大堆。 Integer compareTo
可以被覆盖吗(我不认为可以)?
那么,除了创建另一个 class MyInteger extends Integer{...}
并在那里覆盖它之外,我还能做什么。
最佳答案
你可以让你的堆接受 Comparator在构造函数中,然后提供一个颠倒顺序的比较器。
这就是比较器的实际用途 - 为给定类定义一个非自然顺序的顺序,能够为同一类定义多个顺序,或者确实为一个您无法修改的类定义一个顺序。
在构造时接受比较器的方法可以在TreeSet中看到。例如。
示例代码 stub :
public class Heap<T> { /* no need for items to extend Comparable anymore */
private final Comparator<T> cmp;
public Heap(Comparator<T> cmp) {
this.cmp = cmp;
...
}
...
}
... 然后在您现在使用 item2.compareTo(item2)
的任何地方使用 cmp.compare(item1, item2)
。
关于java - 覆盖整数比较对象?还是骗人?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33640130/