Proritetskø implementeret som heap

Tja, den her virker:

public class PriorityQueue {
    private class PriorityQueueElement {
        public final int priority;
        public final Object object;
        public PriorityQueueElement(int p, Object o) {
            this.priority = p;
            this.object = o;
        }

    }

    private PriorityQueueElement[] elements;
    private int size=0;
    /** Creates new PriorityQueue */
    public PriorityQueue(int size) {
        // Waste the zero element, its a heap.
        elements = new PriorityQueueElement[size+1];
    }
   
    public boolean isEmpty() {
        // First (zero) element is unused in heap.
        return size==0;
    }
    public boolean isFull() {
        return size==elements.length-1;
    }
   
    public int getSize() {
        return size;
    }

    public int topPriority() throws PriorityQueueEmptyException{
        if (isEmpty()) throw new PriorityQueueEmptyException(\"Queue is empty\");
        return elements[1].priority;
    }
   
    public Object dequeue() throws PriorityQueueEmptyException {
        if (isEmpty()) throw new PriorityQueueEmptyException(\"Queue is empty\");
       
        PriorityQueueElement result = elements[1];
        // Swap with the last one, remove the last and reheap
        swap(1, size);
        elements[size] = null;
        size--;
        if (!isEmpty())
            reheap();
        return result.object;
    }
   

    public void enqueue(int priority, Object element )
        throws PriorityQueueFullException {
        if (isFull()) throw new PriorityQueueFullException(\"Unable to add \" + element);
        elements[++size] = new PriorityQueueElement(priority, element);
        reheap();
    }
   
    private void swap(int idx1, int idx2) {
        PriorityQueueElement temp = elements[idx1];
        elements[idx1] = elements[idx2];
        elements[idx2] = temp;
    }
   
    private void reheap() {
          // Only heap non-leaf nodes within the \"current\" heap
        for (int i = size/2;i>0;i--)
        heap(i);
    }
   
    private void heap(int hole) {
          if (hole*2>size)
              return;
         
        int child = hole * 2;
        if( child != size && elements[child+1].priority >
                            elements[child].priority )
              child++;
         
                   
          if(elements[child].priority >
                elements[hole].priority)
          {
              swap(child, hole);
            heap(child);
          }
    }
   
    /*
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue(20);
       
        try {
            for (int i = 0 ; i <21 ; i++) {
                System.out.println(\"Enquing \" + i);
                int rnd = 1 + (int) (Math.random() * 35);
                pq.enqueue(i, \"Hej verden (\"+i+\")\");
            }
        } catch (PriorityQueueException e) {e.printStackTrace();}
        try {
            for (int i = 0 ; i <21 ; i++) {
                System.out.print(pq.topPriority());
                System.out.println(\"->\" +pq.dequeue());
            }
        } catch (PriorityQueueException e) {e.printStackTrace();}
    }
    */
}

class PriorityQueueException extends Exception {
    public PriorityQueueException(String msg) { super(msg); }
}
class PriorityQueueEmptyException extends PriorityQueueException {
    public PriorityQueueEmptyException(String msg) { super(msg); }
}
class PriorityQueueFullException extends PriorityQueueException {
    public PriorityQueueFullException(String msg) { super(msg); }
}

logical >> den der reheap() funktion er da et gevaldigt spild af tid.

public class PriorityQueue {
    private class PriorityQueueElement {
        public final int priority;
        public final Object object;
        public PriorityQueueElement(int p, Object o) {
            this.priority = p;
            this.object = o;
        }
    }

    private PriorityQueueElement[] elements;
    private int size=0;

    public PriorityQueue(int size) { // Creates new PriorityQueue
        // Waste the zero element, its a heap.
        elements = new PriorityQueueElement[size+1];
    }
 
    public boolean isEmpty() { // First (zero) element is unused in heap.
        return size==0;
    }
    public boolean isFull() {
        return size==elements.length-1;
    }
 
    public int getSize() {
        return size;
    }

    public int topPriority() throws PriorityQueueEmptyException{
        if (isEmpty()) throw new PriorityQueueEmptyException(\"Queue is empty\");
        return elements[1].priority;
    }
 
    public Object dequeue() throws PriorityQueueEmptyException {
        if (isEmpty()) throw new PriorityQueueEmptyException(\"Queue is empty\");
     
        PriorityQueueElement result = elements[1];
        // Swap with the last one, remove the last and reheap
        swap(1, size);
        size--;
        heapSink(1);
        return result.object;
    }
 
    public void enqueue(int priority, Object element )
        throws PriorityQueueFullException {
        if (isFull()) throw new PriorityQueueFullException(\"Unable to add \" + element);
        elements[++size] = new PriorityQueueElement(priority, element);
        heapBubble(size);
    }
 
    private void swap(int idx1, int idx2) { // brug elements[0] til swap
        elements[0]    = elements[idx1];
        elements[idx1] = elements[idx2];
        elements[idx2] = elements[0];
    }
 
    private void heapSink(int hole) { // sink from front
        var limit = size /2;
        while ( hole <= limit && heapStep( hole ) { hole *= 2; }
    }

    private void heapBubble(int hole) { // rise from bottom
        do { hole /= 2; } while ( hole > 0 && heapStep( hole );
    }

    private boolean heapStep( int hole ) {
        var child = hole *2;
        if( child < size && elements[child+1].priority > elements[child].priority ) child++;
        if( elements[child].priority <= elements[hole].priority) return false
        swap(child, hole);
        return true;
    }
 
    /*  til test.
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue(20);
     
        try {
            for (int i = 0 ; i <21 ; i++) {
                System.out.println(\"Enquing \" + i);
                int rnd = 1 + (int) (Math.random() * 35);
                pq.enqueue(i, \"Hej verden (\"+i+\")\");
            }
        } catch (PriorityQueueException e) {e.printStackTrace();}
        try {
            for (int i = 0 ; i <21 ; i++) {
                System.out.print(pq.topPriority());
                System.out.println(\"->\" +pq.dequeue());
            }
        } catch (PriorityQueueException e) {e.printStackTrace();}
    }
    */
}

class PriorityQueueException extends Exception {
    public PriorityQueueException(String msg) { super(msg); }
}
class PriorityQueueEmptyException extends PriorityQueueException {
    public PriorityQueueEmptyException(String msg) { super(msg); }
}
class PriorityQueueFullException extends PriorityQueueException {
    public PriorityQueueFullException(String msg) { super(msg); }
}

Ups.

    private void heapSink(int hole) { // sink from front
        var limit = size /2;
        while ( hole <= limit && (hole=heapStep( hole )) > 0 ) { }
    }

    private void heapBubble(int hole) { // rise from bottom
        do { hole /= 2; } while ( hole > 0 && heapStep( hole ) > 0 );
    }

    private int heapStep( int hole ) {
        var child = hole *2;
        if( child < size && elements[child+1].priority > elements[child].priority ) child++;
        if( elements[child].priority <= elements[hole].priority) return 0
        swap(child, hole);
        return child;
    }

mvh JakobA

JakobA>> Jeg ved det. Det var en som blev lavet en gang for at illustrere muligheden for at bruge rekursion til heap. Jeg har aldrig sagt den var optimal :-)

Men det er lidt kedeligt at lave folks lektier her på stedet :-)