min Haufen nicht

Question

arbeiten ich Objekte von Bogentyp zu schaffen und es in die Halde legen, die sie in aufsteigender Reihenfolge sortieren sollte, aber die Ausgabe sollte nicht funktioniert

(B A 4) (B C 8) (B H 11) 

sein, aber es mir dieses

(B A 4) (B H 11) (B C 8) 

geben

dies Arc Klasse

public static class Arc implements Comparable<Arc> { 

    /** 
    * A vertex at one end of this arc. 
    */ 
    Vertex v1; 

    /** 
    * A vertex at one end of this arc. 
    */ 
    Vertex v2; 

    /** 
    * Weight assigned to this arc. 
    */ 
    int weight; 

    /** 
    * Constructs a new Arc object from an existing edge in a graph. 
    * 
    * @param v1 Vertex at one end of the edge. 
    * @param v2 Vertex at the other end of the edge. 
    * @param weight Weight of the edge. 
    */ 
    public Arc(Vertex v1, Vertex v2, int weight) { 
     this.v1 = v1; 
     this.v2 = v2; 
     this.weight = weight; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (o == null || !(o instanceof Arc)) { 
      return false; 
     } 
     Arc other = (Arc)o; 
     return weight == other.weight && 
       ((v1.name.equals(other.v1.name) && v2.name.equals(other.v2.name)) || 
       (v1.name.equals(other.v2.name) && v2.name.equals(other.v1.name))); 
    } 

    /** 
    * Compares the weight of this arc with that of another. 
    * 
    * @param other Other arc 
    * @return 0 if the weights are equal, +ve if this arc's weight is greater, -ve otherwise 
    * 
    */ 
     @Override 
    public int compareTo(Arc other) { 
     return weight - other.weight; 
    } 

    /* (non-Javadoc) 
    * @see java.lang.Object#toString() 
    */ 
     @Override 
    public String toString() { 
     return "(" + v1 + " " + v2 + " " + weight + ")"; 
    } 
} 

dies min Haufen Klasse

public class MinHeap<T extends Comparable<T>> implements Iterable<T> { 

    private ArrayList<T> items; 

    /** 
    * Constructs a new, empty heap with an initial capacity of 10 
    */ 
    public MinHeap() { 
     this(10); 
    } 


    public void siftUp(int k) { // sift up starting at k 
     while (k > 0) { 
      int p = (k-1)/2; 

      int c = items.get(k).compareTo((items.get(p))); 
      if (c < 0) { 
       T temp = items.get(k); 
       items.set(k, items.get(p)); 
       items.set(p, temp); 
       k = p; 
      } else { 
       break; 
      } 
     } 
    } 

    /** 
    * Inserts an item into the heap. 
    * 
    * @param item Item to insert. 
    */ 
    public void insert(T item) { 
     items.add(item); 
     siftUp(items.size()-1); 
    } 


    /** 
     * Returns (but does not remove) the min item in the heap. 
     * 
     * @return Item at top of heap. 
     * @throws NoSuchElementExcepton If heap is empty. 
     */ 
    public T getMin() throws NoSuchElementException { 
     if (items.isEmpty()) { 
      throw new NoSuchElementException(); 
     } 
     return items.get(0); 
    } 

    public String toString() { 
     String ret = ""; 
     for (T item: items) { 
      ret += " " + item; 
     } 
     return ret; 
    } 
} 

Answer 1

Es scheint, als ob Sie das Konzept der Min-Heaps missverstanden haben.

Ein Heap sortiert die Elemente nicht, es ist nur eine Datenstruktur, die den übergeordneten Knoten kleiner als seine untergeordneten Elemente hält. Dies bedeutet nicht, dass die Elemente im Heap in sortierter Reihenfolge gespeichert werden. Wenn Sie jedoch eine Methode zum Entfernen des min-Elements implementieren, die auch in O(log(n)) ausgeführt wird, können Sie Daten in O(n log(n)) sortieren, indem Sie jedes Element in den Heap einfügen und einzeln abrufen und entfernen, was zur Rückgabe führt aufsteigende Reihenfolge.