Implémentation de tas correcte dans une file d'attente prioritaire

Question

Mon problème est plus sémantique que fonctionnel, car le code semble implémenter correctement les fonctions deQueue et enQueue.

Les fonctions de reheapDown et reheapUp sont utilisés de manière incorrecte, et je crois que le problème réside dans ma fonction de tas

package priqueue; 

public class Hosheap{ 
    private Patient[] elements; 
    private int numElements; 

    public Hosheap(int maxSize) 
    { 
    elements= new Patient[maxSize]; 
    numElements=maxSize; 
    } 

    public void ReheapDown(int root,int bottom) 
    { 
    int maxChild; 
    int rightChild; 
    int leftChild; 
    leftChild=root*2+1; 
    rightChild=root*2+2; 

    if (leftChild<=bottom) 
    { 
     if(leftChild==bottom) 
     maxChild=leftChild; 
     else 
     { 
     if(elements[leftChild].getPriority() <= elements[rightChild].getPriority()) 
      maxChild=rightChild; 
     else 
      maxChild=leftChild; 
     } 
     if(elements[root].getPriority()<elements[maxChild].getPriority()) 
     { 
     Swap(root,maxChild); 
     ReheapDown(maxChild,bottom); 
     } 
    } 
    } 

    public void ReheapUp(int root,int bottom) 
    { 
    int parent; 
    if(bottom>root) 
    { 
     parent=(bottom-1)/2; 
     if(elements[parent].getPriority()<elements[bottom].getPriority()) 
     { 
     Swap(parent,bottom); 
     ReheapUp(root,parent); 
     } 
    } 
    } 

public void Swap(int Pos1, int Pos2) 
{ 
    Patient temp; 
    temp = elements[Pos1]; 
    elements[Pos1]=elements[Pos2]; 
    elements[Pos2]=temp; 
} 

public Patient getElement(int e) 
{ 
    return elements[e]; 
} 

public void setElement(Patient p, int n) 
{ 
    elements[n]=p; 
} 
} 

L'idée est de réorganiser un système simple de file d'attente prioritaire donc quand on enlève un objet patient, ReheapUp ou vers le bas réorganise correctement la file d'attente, que le code n'atteint pas. Dois-je également inclure le code de file d'attente prioritaire, Ou est-ce déjà trop long? J'utilise NetBeans IDE 6.0.1, Si cela peut vous aider.

Answer 1

Pas exactement répondre à votre question, mais avec Java, vous pouvez regarder dans les classes de collection intégrées. Vous pouvez obtenir un comportement de file d'attente prioritaire mais en utilisant un TreeSet (un type d'ensemble ordonné) et en implémentant un comparateur personnalisé pour les instances Patient. Selon ce que vous essayez d'atteindre, cela peut être préférable. Il ressemblerait à quelque chose comme ceci:

En Patient.java ...

class Patient implements Comparator { 
... 
public int compareTo(Patient other) { 
    return getPriority() > other.getPriority() ? 1 : 0; 
} 

Ensuite, à l'endroit que vous souhaitez utiliser la file d'attente

Set<Patient> queue = new TreeSet<Patient>(); 
queue.add(p1); 
queue.add(p2); 
//traverse in order of priority 
for(Patient p : queue) { 
    doStuff(); 
} 

Answer 2

En fonction de vos besoins d'utilisation, la réponse relatives à TreeSets feront très probablement ce que vous voulez.

Cependant si vous vraiment besoin d'une file d'attente, par opposition à une collection triée, alors le PriorityQueue intégré peut être utile.

Answer 3

Voici une implémentation simple d'un PriorityHeap. Je l'ai codé assez rapidement donc il peut y avoir quelques failles mais j'ai implémenté la logique pushUp() et pushDown().

import java.util.Random; 

public class Heap { 

    private Double[] data; 
    private int lastItem; 

    public Heap(int initialSize) { 
     // to simplify child/parent math leave the first index empty 
     // and use a lastItem that gives us the size 
     data = new Double[initialSize]; 
     lastItem = 0; 
    } 

    public void insert(Double d) { 
     // double size if needed 
     // should have a matching shrink but this is example code 
     if (lastItem + 1 >= data.length) { 
      Double[] doubled = new Double[data.length * 2]; 
      System.arraycopy(data, 0, doubled, 0, data.length); 
      data = doubled; 
     } 
     data[lastItem + 1] = d; 
     lastItem++; 
     pushUp(lastItem); 
    } 

    public void pushDown(int index) { 

     if (lastItem > 1) { 

      int leftChildIndex = index * 2; 
      int rightChildIndex = leftChildIndex + 1; 

      // assume that neither child will dominate (in priority) 
      // the item at index 
      int indexToPromote = index; 
      // there may not be a left child 
      if (leftChildIndex <= lastItem) { 

       Double leftChild = data[leftChildIndex]; 
       Double tmp = data[index]; 
       if (tmp.compareTo(leftChild) < 0) { 
        indexToPromote = leftChildIndex; 
       } 

       // there might not be a right child 
       if (rightChildIndex <= lastItem) { 
        Double rightChild = data[rightChildIndex]; 
        tmp = data[indexToPromote]; 
        if (tmp.compareTo(rightChild) < 0) { 
         indexToPromote = rightChildIndex; 
        } 
       } 
      } 

      // did either child dominate the item at index 
      // if so swap and push down again 
      if (indexToPromote != index) { 
       swap(index, indexToPromote); 
       pushDown(indexToPromote); 
      } 
     } 
    } 

    public void pushUp(int index) { 
     if (index > 1) { 
      // equivalent to floor((double)index/2.0d); 
      // if item at index is greater than its parent 
      // push the item up to until if finds a home 
      int parentIndex = index >>> 1; 
      Double parent = data[parentIndex]; 
      Double item = data[index]; 
      if (item.compareTo(parent) > 0) { 
       swap(parentIndex, index); 
       pushUp(parentIndex); 
      } 
     } 
    } 

    public Double removeTop() { 
     // assume size is zero then examine other cases 
     Double top = null; 
     if (lastItem > 1) { 
      // save the top item and take the bottom item and place it 
      // at the top the push the new top item down until it 
      // finds a home 
      top = data[1]; 
      Double bottom = data[lastItem]; 
      lastItem--; 
      data[1] = bottom; 
      pushDown(1); 
     } else if (lastItem == 1) { 
      top = data[1]; 
      lastItem--; 
     } 
     return top; 
    } 

    public int size() { 
     return lastItem; 
    } 

    private void swap(int index1, int index2) { 
     Double temp = data[index1]; 
     data[index1] = data[index2]; 
     data[index2] = temp; 
    } 

    public static void main(String[] args) { 
     Heap heap = new Heap(4); 
     Random r = new Random(); 
     for (int i = 0; i < 100000; i++) { 
      Double d = Double.valueOf(r.nextDouble() * 100.0d); 
      heap.insert(d); 
     } 
     double max = Double.MAX_VALUE; 
     while (heap.size() > 0) { 
      Double top = heap.removeTop(); 
      if (top.doubleValue() > max) { 
       System.out.println("bad ordering..."); 
      } 
      max = top.doubleValue(); 
      System.out.println(max); 
     } 
     System.out.println("done..."); 
    } 
}