java - 使用抽象类构建堆

Question

我对抽象类代码的实际实现及其意义有点困惑。

我为最大堆编写了代码，我想基于它创建一个抽象类，这样我就可以得到一个不仅仅是“最大”堆的堆的总体轮廓。

我的 MaxHeap 的主体如下所示:

public class MaxHeap {

    // A class for nodes, just has 3 fields, lchild, rchild, and value
    private HeapNode top;
    private List<HeapNode> heap;

    public MaxHeap() {
        this.top = null;
        this.heap = new ArrayList<>();
    }

    //I won't go into the guts of these methods, but will explain

    //Displays the heap like [1,2,3,4,5,...]
    public void display() {...}

    //Adds a new HeapNode to the end of heap, if empty sets to top
    public void add(int value) {...}

    //Deletes a HeapNode at index pos
    public void delete(int pos) {...}

    //Swaps 2 Nodes within the heap
    protected void swap(int pos, int otherPos) {...}

    //// These are the methods that actually differ depending on the
    //// type of heap (maxheap, minheap, etc) so I would assume they
    //// would be abstract methods if writing an abstract class?
    |
    |
    V

    //Called within add method, heapifys the heap after adding a new Node
    protected void addHeapify(int pos) {...}

    //Called within delete method, heapifys the heap after deleted Node
    protected void deleteHeapify(int pos) {...}

    //Called within deleteHeapify for "if (pos==0) {...}", delete max Node
    protected deleteExtremum() {...}
}

我的问题反射(reflect)了我将如何在更抽象的层面上实现这一点？我想将我的编码提升到一个新的水平，并且需要理解这一点。我会创建一个这样的抽象类吗？

public abstract class Heap {

private HeapNode top;
private List<HeapNode> heap;

public Heap() {...}

// **************
// public methods
// **************

public void display() {...}
public void add(int value) {...}
public void delete(int pos) {...}

// ******************
// non-public methods
// ******************

protected void swap(int pos, int otherPos) {...}

// ****************
// abstract methods
// ****************

protected abstract void addHeapify(int pos);
protected abstract void deleteHeapify(int pos);
protected abstract void deleteExtremum();

}

理解“抽象化”原始类的正确方法将对我有很大帮助。

在抽象类中添加字段和构造函数是否正确，即使添加、删除、交换和显示在不同的堆中不会改变，这些方法也应该是抽象的吗？

我还想知道是否应该使用接口(interface)，但它似乎是一个更严格的抽象类，而且我无法定义添加、删除、交换和显示。

Answer 1

抽象类是几个具体类的概括。它用于共享通用功能和数据。由于它是抽象的，如果没有一些定制，它就不能被实例化(使用)。如果该类可以按原样使用，则它不是抽象的。

如果您需要针对接口(interface)的抽象类，那么重要的一点是抽象是否包含数据。您可以拥有带有数据字段和仅抽象方法的抽象类。

当您的通用功能需要一些特定于继承者的数据或处理时，应使用抽象方法。就像您的 add 方法由于某种原因需要调用 addHeapify 一样，但不关心它的实现方式。

如果您需要所有后代都有某种方法，但它不在通用功能中使用，那么使用接口(interface)是明智的，因为接口(interface)定义了类应该如何行为，但没有定义它包含哪些数据。因此，您可以抽象出两个包含不同数据的类。在 Java 8 中，您可以直接在接口(interface)中实现默认方法(以前这是不可能的)，因此仅当您有公共(public)数据要存储在其中时才需要抽象类。

请记住，其他算法可以使用对抽象类或接口(interface)的引用来调用您的抽象类或接口(interface)，而无需知道引用背后的实现是什么。这主要用于使代码可变，因为您可以替换接口(interface)或抽象类的任何实现，而无需更改客户端代码。