0

我正在编写一个 Heap（Max-Heap，意思是最大元素是根）类，可用于“堆化”给定的一组对象。我知道这个堆的一般结构以及各种算法。现在对于一般对象，没有定义比较。所以我需要定义两个对象之间的比较。我的问题是这个比较函数应该定义在类堆中还是类对象中？如果我在堆类中定义它，那么对于我使用的每个数据结构，我都需要重写效率不高的比较函数。这是因为如果我稍微更改对象，我最终可能会在大量位置更改比较。那么这件事情是怎么处理的呢？谢谢你。

 class Object{
     int value;
     Object (int a) {
         value=a;
     }

     boolean isLessThan(Object a, Object b){
         if (a.value<=b.value){
             return true;
         }
         else return false;
     }
 }

 class Heap{
     Object [] heap=new Object[1000];
     int size=0;
     Heap() {        
     }

     void HeapifyDownwards (int index){
         int left_child=2*index+1;
         int right_child=2*index+2;

         if (size>right_child){
             // both right and left child exist
             Object right= heap[right_child];
             Object left= heap[left_child];
             Object node = heap[index];

             if ((isLessThanEqualTo(right,node)) && (isLessThanEqualTo(left,node))){
                 return;
             }
         }
         else if (size==right_child){
             //only left child exists
         } 
         else {
             // no child exists
         }
     }
 }
4

2 回答 2

1

在 Java 中处理此类事情的一般方式是：

  1. 限制存储在数据结构中的元素实现Comparable，或
  2. 在堆对象中存储一个比较器（在构造时设置）。

以Java API中的 TreeSet 类为例。

请注意，因为 Java 是（大部分）静态类型语言，所以对这种数据结构使用泛型非常普遍。它们可能值得学习，尽管我可以理解让堆类为特定类型的对象工作的愿望。

此外，如果本练习的目的是了解堆的工作原理，那就太好了。如果你真的想要一个 Java 应用程序的优先级队列，Java 已经有一个PriorityQueue类。

于 2012-11-09T06:16:29.683 回答
0

行！解决方案是使用 Comparable 而不是 Objects。然后使用 node.compareTo(right) （等）进行比较！

有关更多详细信息，请参阅此链接： Java 中的抽象对象比较

public class Heap{
    Comparable [] heap=new Comparable[1000];
    int size=0;
    Heap() {        
    }
    public void HeapifyDownwards (int index){
        int left_child=2*index+1;
        int right_child=2*index+2;

        Comparable right= heap[right_child];
        Comparable left= heap[left_child];
        Comparable node = heap[index];

        if (size>right_child){
            // both right and left child exist
            if ((node.compareTo(right)>0) && (node.compareTo(left)>0)){
                return;
            }
            else if ((right.compareTo(node)>0) && (right.compareTo(left)>0)){
                Comparable temp=right;
                heap[right_child]=node;
                heap[index]=temp;
                HeapifyDownwards(right_child);
            }
            else if ((left.compareTo(node)>0) && (left.compareTo(right)>0)){
                Comparable temp=left;
                heap[left_child]=node;
                heap[index]=temp;
                HeapifyDownwards(left_child);
            }
        }
        else if (size==right_child){
            //only left child exists
            if (left.compareTo(node)>0){
                Comparable temp=left;
                heap[left_child]=node;
                heap[index]=temp;
                HeapifyDownwards(left_child);
            }
            else {return;}
        } 
        else {
            return;
        }
    }
    public void HeapifyUpwards (int index){
        int parent_index=(index-1)/2;

        Comparable parent= heap[parent_index];
        Comparable node = heap[index];

        if (node.compareTo(parent)>0){
            Comparable temp= parent;
            heap[parent_index]=node;
            heap[index]=temp;
            HeapifyUpwards(parent_index);
        }
        else{
            return;
        }
    }
    public void Insert (Comparable in){
        heap[size]=in;
        size++;
        HeapifyUpwards(size-1);
    }
    public Comparable Remove (){
        Comparable out=heap[0];
        heap[0]=heap[size-1];
        size--;
        HeapifyDownwards(0);
        return out;
    }
}


public class TestObject implements Comparable{
    int value;
    TestObject (int a) {
        value=a;
    }

    @Override
    public int compareTo (Object b){
         if (this.getClass() == b.getClass()){
            TestObject b_test = (TestObject) b;
            if (this.value<b_test.value){
                return -1;
            }
            else if(this.value==b_test.value){
                return 0;
            }
            else return 1;
         }
         else return -1;
    }

    public void Print (){
        System.out.println(value);
    }
}
于 2012-11-09T10:25:07.090 回答