Priority Queue implementation using a heap. The queue consists of items, each item has a unique ID (to tell them apart) and a priority.

public class Item {
    private static int count = 1; 
    private int id;
    private int priority;

    public Item(int thepriority) {
	id = count;
	count++;
	priority = thepriority;
    }

    public int getPriority() {
	return priority;
    }

    public int getId() {
	return id;
    }
}


The new corrected code for the PriorityHeap class - Oct. 11th.
And corrected again - Nov. 19th.

public class PriorityHeap {
    private final int capacity = 128;
    private Item [] items = new Item[capacity]; 
    private int length;
    
    public PriorityHeap() {
	// do nothing
    }

    public boolean isEmpty() {
	return (length == 0);
    }

    public void enqueue(int priority) { 
	if (length >= capacity) {
	    System.out.println("Queue overflow");
	    System.exit(0);
	}
	Item newItem = new Item(priority);
	// System.out.println("Adding " + newItem.getId());
	items[length] = newItem;
	int k = length;
	int i = parent(k);
	while (i >= 0 && items[k].getPriority() > items[i].getPriority()) {
	    //System.out.println("exchanging " + items[k].getId() + " with " +
	    //	       items[i].getId());
	    Item temp = items[k];
	    items[k] = items[i];
	    items[i] = temp;
	    k = i;
	    i = parent(i);
	}
	length++;
    }

    public int dequeue() {
	if (length < 1) {
	    System.out.println("Queue underflow");
	    System.exit(0);
	}
	// save away the item to be returned
	Item max = items[0];
	// move the last element to the root of the tree
	items[0] = items[length-1];
	int k = 0;
	int left = 1; // left subtree of the root
	int right = 2; // right subtree of the root

	while (left < length - 1 && right < length - 1 && 
	       (items[k].getPriority() < items[left].getPriority() || 
		items[k].getPriority() < items[right].getPriority()))  {
	    if (items[left].getPriority() >= items[right].getPriority()) {
		Item temp = items[k];
		items[k] = items[left];
		items[left] = temp;
		k = left; // line moved to the correct position: Nov. 19th
		right = rightChild(left);
		left = leftChild(left);
		// k = left;
	    } else {
		Item temp = items[k];
		items[k] = items[right];
		items[right] = temp;
		k = right;  // line moved to the correct position: Nov. 19th
		left = leftChild(right);
		right = rightChild(right);
		// k = right;
	    }
	}

	// exchanging with the last (incomplete) level elements
	// This is the case when right >= length - 1
	if (left < length - 1 && 
	       items[k].getPriority() < items[left].getPriority()) {
	    Item temp = items[k];
	    items[k] = items[left];
	    items[left] = temp;
	}
	--length;
	return max.getPriority();
    }
    
    public void print() {
	for (int i = 0; i < length; ++i) {
	    System.out.print(" id = " + items[i].getId() + " PRI = " 
			     + items[i].getPriority());
	}
	System.out.println();
    }

    // given an index i, returns the parent of the node 
    // at that index
    // returns -1 for the root
    private int parent(int i) {
	if (i <= 0) return -1;
	return (i - 1)/2;
    }

    // given an index i, returns the left child of the node 
    // at that index
    // doesn't check if the node is within the capacity
    private int leftChild(int i) {
	return i * 2 + 1;
    }

    // given an index i, returns the right child of the node 
    // at that index
    // doesn't check if the node is within the capacity
    private int rightChild(int i) {
	return 2 * (i + 1);
    }    
}



public class TestPriorityHeap {
    public static void main(String [] args) {
	PriorityHeap ph = new PriorityHeap();
	ph.enqueue(3);
	ph.enqueue(4);
	ph.enqueue(2);
	ph.enqueue(4);
	ph.enqueue(5);
	ph.print();
	Item fromqueue = ph.dequeue();
	ph.print();
	ph.enqueue(5);
	ph.print();
	// flush the queue
	while (!ph.isEmpty()) {
	    ph.dequeue();
	}
	ph.print();
	// start all over
	ph.enqueue(55);
	ph.enqueue(1);
	fromqueue = ph.dequeue();
	ph.print();
	ph.enqueue(3);
	ph.enqueue(0);
	ph.print();
    }
}


This is an example from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.