堆爲一般對象

Question

我正在寫一堆（Max-Heap，意思是max元素是root）類，它可用於「heapify」給定的一組對象。 我知道這個堆的一般結構以及各種算法。 現在對於一般對象，沒有定義比較。所以我需要定義兩個對象之間的比較。 我的問題是，如果這個比較函數應該在類堆中或在類Object中定義？如果我在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 
     } 
    } 
} 

Answer 1

好的！ 解決方案是使用Comparable而不是Objects。 然後使用node.compareTo（右）（等）進行比較！

請參閱此鏈接的更多細節： Abstract Object Comparison in 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); 
    } 
} 

Answer 2

的一般方式這樣的事情是在Java中處理的內容爲：

1. 限制存儲在數據結構來實現Comparable的元素，或
2. 存儲在堆對象的比較器（在施工時設定）。

查看TreeSet class in the Java API的示例。

請注意，因爲Java是一種（主要是）靜態類型的語言，所以對這種數據結構使用泛型是非常普遍的。他們可能是值得學習的，儘管我可以理解讓堆類爲某種特定對象工作的願望。

另外，如果本練習的目的是學習堆的工作方式，那麼很好。如果您確實需要Java應用程序的優先隊列，則Java已經有一個PriorityQueue類。