使用最大堆实现优先级队列。堆大小固定，并使用数组表示。

import java.util.Arrays;/** from 时 代      J a v a   公   众 号 - nowjava.com**/


public class PriorityQueue {

    int[] heap;

    int size;


    // Constructor initializes instance variables

    public PriorityQueue(int maxSize) {

        heap = new int[maxSize];

        size = 0;

    }


    // Push an element on to the queue

    public void push(int val) {

        // If the queue is full then throw an exception

        if (size == heap.length)

            throw new IllegalStateException();


        // Put the value in the next available space in the queue

        int pos = size;

        heap[pos] = val;/*来 自 n o w j a v a . c o m*/


        // While val is bigger than its parent, swap it with its parent

        while (pos > 0) {

            // Get the parent and compare the values

            int parent = (pos + 1) / 2 - 1;

            if (heap[parent] >= heap[pos])

                break;

            swapIndices(parent, pos);

            pos = parent;

        }


        // We added an element so increment the size

        size++;

    }


    // Pop the max element from the queue

    public int pop() {

        // If the queue is empty, throw an exception

        if (size == 0)

            throw new IllegalStateException();


        // The top of the heap is the first item in the array, so save it off

        // to the side so we don't lose it

        int toReturn = heap[0];


        // Move the bottom item in the heap to the first position. We don't need

        // to remove it from the array because we have the size variable

        heap[0] = heap[size - 1];

        size--;


        // Bubble down the top element to the right spot

        int pos = 0;

        // We're going to be swapping with the children and any pos >= size / 2

        // doesn't have any children

        while (pos < size / 2) {

            int leftChild = pos * 2 + 1;

            int rightChild = leftChild + 1;

            // If the right child exists and is greater than the left child, 

            // compare it to the current position

            if (rightChild < size && heap[leftChild] < heap[rightChild]) {

                // Only swap if the value is less than the child

                if (heap[pos] >= heap[rightChild])

                    break;

                swapIndices(pos, rightChild);

                pos = rightChild;

            } else {

                // Do the same comparison with the left child

                if (heap[pos] >= heap[leftChild])

                    break;

                swapIndices(pos, leftChild);

                pos = leftChild;

            }

        }


        return toReturn;

    }


    // Swap the values at the indices

    private void swapIndices(int i, int j) {

        int temp = heap[i];

        heap[i] = heap[j];

        heap[j] = temp;

    }


    public static void main(String[] args) {

        tester(new int[] {}, "Empty");

        tester(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 }, "Ascending order");

        tester(new int[] { 8, 7, 6, 5, 4, 3, 2, 1 },