java 优先队列
Every now and then we need to process items of a queue in a particular order. Priority queue is a Data Structure that does the job. Java priority queue is different from “normal” queue. Instead of “First-In-First-Out”, it retrieves the items in order of their priority.
 我们有时需要按特定顺序处理队列中的项目。 优先级队列是完成任务的数据结构。 Java优先级队列与“普通” 队列不同 。 代替“先进先出”，它按优先级顺序检索项目。 
 优先队列Java (Priority Queue Java)
The java.util.PriorityQueue class, provides us an implementation of such a data type, by using priority heap implementation internally. Java PriorityQueue is an unbounded queue. It was introduced in Java 1.5 and enhanced in Java SE 8 release. PriorityQueue is internally implemented by following “Priority Heap” data structure.
 java.util.PriorityQueue类通过内部使用优先级堆实现为我们提供了这种数据类型的实现。 Java PriorityQueue是一个无界队列。 它是在Java 1.5中引入的，并在Java SE 8版本中得到了增强。 PriorityQueue通过遵循“ Priority Heap”数据结构在内部实现。 

Here is the PriorityQueue class hierarchy:
 这是PriorityQueue类层次结构： 
PriorityQueue Class Diagram:
 PriorityQueue类图： 
 Java PriorityQueue构造函数 (Java PriorityQueue Constructors)
PriorityQueue() – Creates a PriorityQueue with the default initial capacity, i.e. 11
 PriorityQueue（） –使用默认初始容量（即11 ）创建一个PriorityQueue 
PriorityQueue(Collection c) – Creates a PriorityQueue with the elements in the specified collection
 PriorityQueue（Collection c） –使用指定集合中的元素创建一个PriorityQueue 
PriorityQueue(int initialCapacity) – Creates a PriorityQueue with the specified initial capacity
 PriorityQueue（int initialCapacity） –创建具有指定初始容量的PriorityQueue 
PriorityQueue(int initialCapacity, Comparator comparator) – Creates a PriorityQueue with the provided initial capacity and the ordering of its elements is according to the specified comparator
 PriorityQueue（int initialCapacity，Comparator比较器） –创建具有提供的初始容量的PriorityQueue，其元素的顺序根据指定的比较器 
PriorityQueue(PriorityQueue c) – Creates a PriorityQueue containing the elements in the specified priority queue
 PriorityQueue（PriorityQueue c） –创建一个包含指定优先级队列中元素的PriorityQueue 
PriorityQueue(SortedSet c) – Creates a PriorityQueue containing the elements in the specified sorted set
 PriorityQueue（SortedSet c） –创建一个包含指定排序集中的元素的PriorityQueue 
Priority Queue elements are ordered by their natural ordering unless we provide a Comparator while creating it.

The elements are ordered in ascending order by default, hence the head of the queue is the element whose priority is lowest.
 除非我们在创建Comparator时提供它，否则Priority Queue元素将按照其自然顺序进行排序。 
 默认情况下，元素按升序排列，因此队列的开头是优先级最低的元素。 
If there are two elements which are eligible to become the head at the same time, this kind of ties are broken arbitrarily.
 如果有两个元素可以同时成为负责人，则这种联系会被任意打破。 
 Java PriorityQueue示例 (Java PriorityQueue Example)
Let’s create a PriorityQueue, containing various tasks:
 让我们创建一个PriorityQueue ，其中包含各种任务： 
PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");
This creates a PriorityQueue of tasks, which will be ordered by the natural ordering of String.

Let’s create another PriorityQueue which orders the tasks in reverse order of natural ordering. So we need to pass a Comparator:
 这将创建一个PriorityQueue任务，该任务将按String的自然顺序进行排序。 
 让我们创建另一个PriorityQueue，它以自然顺序的相反顺序对任务进行排序。 因此，我们需要通过一个比较器： 
PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");
 Java PriorityQueue方法 (Java PriorityQueue Methods)
Now, let’s take a look at all the methods available for PriorityQueue and use them:
 现在，让我们看一下PriorityQueue可用的所有方法并使用它们： 
Boolean add(E e) – This method inserts the specified element in the queue.

We have already added 5 tasks in our queue using this method.
 布尔值add（E e） –此方法将指定的元素插入队列。 
 我们已经使用这种方法在队列中添加了5个任务。 
Comparator comparator() – This method returns the Comparator used to order the elements in this queue. It returns null if no comparator was specified and the queue is sorted according to the natural ordering of its elements.

So, if we do:
System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());
The output will be:
 比较器比较器（） -此方法返回用于对队列中的元素进行排序的比较器 。 如果未指定比较器，并且队列根据其元素的自然顺序排序，则返回null。 
 因此，如果我们这样做： 
System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());
 输出将是： 
boolean contains(Object o) – Returns true if the queue contains the specified element.

Let’s check if “task3” belongs to the Priority queue tasks:
System.out.println(tasks.contains("task3"));
This prints:
 boolean contains（Object o） –如果队列包含指定的元素，则返回true。 
 让我们检查“ task3”是否属于优先级队列任务： 
System.out.println(tasks.contains("task3"));
 打印： 
boolean offer(E e) – Just like the add() method, this method also adds an element to the queue.

The offer() and add() methods are actually a bit different for capacity constrained queues, but in case of PriorityQueue, both are same. Unlike add(), offer() does not throw an exception even if it fails to add the element in the queue.
 boolean offer（E e） –就像add（）方法一样，此方法也将元素添加到队列中。 
 对于容量受限制的队列，offer（）和add（）方法实际上有些不同，但是对于PriorityQueue，两者是相同的。 与add（）不同，即使offer（）无法将元素添加到队列中，它也不会引发异常。 
E peek() – Retrieves the head of this queue, or returns null if this queue is empty. In other words, it returns the element with highest priority.

So the following code:
System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());
Gives us:
 E peek（） –检索此队列的开头，如果此队列为空，则返回null。 换句话说，它返回具有最高优先级的元素。 
 所以下面的代码： 
System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());
 给我们： 
E poll() – This method also retrieves the head of the queue(element with highest priority), or returns null if the queue is empty. But unlike peek(), it also removes the element.

So, if we call poll():
System.out.println(“Poll on tasks: ”+tasks.poll());
System.out.println(“Poll on reverseTasks: ”+reverseTasks.poll());
And then peek:
We’ll have the following outptut:
Poll on tasks: task1
Poll on reverseTasks: task5
Peek on tasks: task2
Peek on reverseTasks: task4
 E poll（） –此方法还检索队列的头部（具有最高优先级的元素），如果队列为空，则返回null。 但是与peek（）不同，它还删除了元素。 
 因此，如果我们调用poll（）： 
 然后偷看： 
System.out.println(“Peek on tasks: ”+tasks.peek());
System.out.println(“Peek on reverseTasks: ”+reverseTasks.peek());
 我们将提供以下输出： 
int	size() – Returns the number of elements in the queue.
 int size（） –返回队列中元素的数量。 
boolean remove(Object o) – Removes the specified element from the queue, if it’s present. If two same elements are present, it only removes one of them.
 boolean remove（Object o） -从队列中删除指定的元素（如果存在）。 如果存在两个相同的元素，则仅删除其中之一。 
Object[] toArray() – Returns an array containing all the elements in the queue.
 Object [] toArray（） –返回包含队列中所有元素的数组。 
T[] toArray(T[] a) – Returns an array containing all the elements in the queue, and the type of the returned array is that of the specified array.
 T [] toArray（T [] a） –返回包含队列中所有元素的数组，并且返回的数组的类型为指定数组的类型。 
Iterator iterator() – Returns an iterator for the queue.
 Iterator iterator（） –返回队列的迭代器。 
void clear() – Removes all of the elements from the queue.
 void clear（） –从队列中删除所有元素。 
Apart from these, the PriorityQueue also inherits the methods from the Collection and Object classes.
 除此之外， PriorityQueue还继承了Collection和Object类的方法。 
 Java PriorityQueue时间复杂度 (Java PriorityQueue Time Complexity)
For enqueing and dequeing methods, the time complexity is O(log(n))
 对于入队和出队方法，时间复杂度为O（log（n）） 
For the remove(Object) and contains(Object) methods, the time complexity is linear
 对于remove（Object）和contains（Object）方法，时间复杂度是线性的 
For the retrieval methods, it has constant time complexity
 对于检索方法，它具有恒定的时间复杂度 
This implementation of priority queue is not thread-safe. So, if we need synchronised access, we need to use PriorityBlockingQueue.
 优先级队列的此实现不是线程安全的。 因此，如果需要同步访问，则需要使用PriorityBlockingQueue 。 
Reference: API Doc
 参考： API文档 
翻译自: https://www.journaldev.com/16254/priority-queue-java
java 优先队列

PriorityQueue，也就是优先队列，所谓的优先队列，就是在队列中根据某一个特征值自动进行排序，优先队列分为两种，最大优先队列和最小优先队列，优先队列的一个最大特性就是，当插入元素或者删除元素的时候，队列会自动进行调整，保证队首元素一定是优先权最大/最小。正是由于优先队列的这种特性，优先队列可以被用在很多地方，比如作业调度，进程调度等。







堆与堆排序

优先队列的内部是采用堆这一种数据结构来实现的，并且，在进行操行的时候，时刻进行堆的维护。

比较常用的一种堆结构是二叉堆，二叉堆的实质是一个二叉树，只不过这个二叉树有点特殊，每一个父子节点都是其子孙节点中的最大值，称之为最大堆，反之则称之为最小堆，下面采用最大堆来演示，最小堆原理相同，二叉堆一般采用数组来进行维护即可，并且，由于其本身的特性，可以得出结论，堆的左孩子索引为 i * 2+1， 右孩子索引为 i * 2 + 2,其中i为父亲节点的索引

从图中可以看到，每一个父子节点的值都比其子孙节点大，也就是说，根节点的值是整个堆中的值最大的一个，这就是最大

堆名字的由来了

建立二叉堆的方法非常简单，根据二叉堆的特性，只需要对每个元素执行调整即可，调整的具体过程为，从后往前调整，如果发现一个元素的值比其孩子节点(左右孩子)的值小，则跟其进行交换，并且递归其发生交换的孩子，继续进行判断，交换，直至到达第一个元素，不过这里有一个可以提高效率的地方，从元素个数/2-1开始即可

二叉堆排序是根据堆的这种特性而出现的一种排序算法，算法的流程为，首先建立二叉堆，然后每次交换第一个元素(也就是当前的最大值)与最后一个元素，调整堆，将堆的大小-1，重复上面的操作，直至堆大小为1，具体代码如下：








优先队列(PriorityQueue)源码剖析

首先是构造方法

    // 无参构造器，默认大小为11
    public PriorityQueue() {
        // DEFAULT_INITIAL_CAPACITY = 11;
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    // 指定大小的构造器
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    // 提供一个比较器构造器
    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

    // 指定容量并且提供一个比较器的构造器
    public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

    // 使用容器中的数据来构造优先队列
    // 其中的SortedSet将在后面学习
    // 从这里可以看到，如果建立的元素已经是有序的，也就是已经提供了比较器，则直接使用
    // 如果不是，则按照默认的方式进行堆的建立
    public PriorityQueue(Collection<? extends E> c) {
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        else if (c instanceof PriorityQueue<?>) {
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }
        else {
            this.comparator = null;
            initFromCollection(c);
        }
    }

    // 使用另一个优先队列来构造
    public PriorityQueue(PriorityQueue<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initFromPriorityQueue(c);
    }

    // 使用SortedSet来构造
    public PriorityQueue(SortedSet<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initElementsFromCollection(c);
    }

    // 从优先队列构造
    private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
        if (c.getClass() == PriorityQueue.class) {
            this.queue = c.toArray();
            this.size = c.size();
        } else {
            initFromCollection(c);
        }
    }

    // 从容器中构造，并且建立堆
    private void initFromCollection(Collection<? extends E> c) {
        initElementsFromCollection(c);
        heapify();
    }

    // 从容器中构造
    private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if (a.getClass() != Object[].class)
            a = Arrays.copyOf(a, a.length, Object[].class);
        int len = a.length;
        if (len == 1 || this.comparator != null)
            for (int i = 0; i < len; i++)
                if (a[i] == null) // 不能包含空元素
                    throw new NullPointerException();
        this.queue = a;
        this.size = a.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

堆的建立与调整

    // 建立堆
    private void heapify() {
        // 从非叶子节点进行调整
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }

    // 如果提供了比较器，则使用比较器进行堆调整
    // 否则，使用默认的比较器进行堆调整
    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

    // 使用比较器进行堆调整，可以看到，实现方式跟上面的调整方式基本一样
    private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        // 从上往下开始调整
        while (k < half) {
            int child = (k << 1) + 1;
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
            // 这里需要注意的是，默认建立的是最小堆
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }

    // 如果没有提供比较器，则使用元素默认的构造器
    // 这也就意味着传入的元素必须是实现了Comparable接口
    // 并且已经实现compareTo方法
    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

插入元素
public class Heap {
	private int[] data;
	private int heapSize;

	public Heap(int[] data, int heapSize) {
		this.data = data;
		this.heapSize = heapSize;
	}

	// 建立二叉堆
	private void buildHeap() {
		// 从索引为堆大小/2 - 1 开始，调整元素的位置
		for (int i = (heapSize >>> 1) - 1; i >= 0; i--) {
			heap(i);
		}
	}

	// 建立二叉堆的具体实现
	private void heap(int i) {
		int left = (i << 1) + 1; // 左孩子索引(2*n + 1)
		int right = left + 1; // 右孩子索引(2*n + 2)
		int max = i;
		// 如果左孩子的值比父亲的值大，则记录下左孩子索引
		if (left < heapSize && data[left] > data[i]) {
			max = left;
		}
		// 如果右孩子的值比当前的最大值大，则记录下其索引
		if (right < heapSize && data[right] > data[max]) {
			max = right;
		}
		// 如果孩子的值比父亲大，则进行交换
		// 否则，则结束，表明已经是最大堆了
		if (max != i) {
			int tmp = data[i];
			data[i] = data[max];
			data[max] = tmp;
			// 递归发生交换的孩子节点
			heap(max);
		}
	}
	
	 // 堆排序
    public void sort(){
        // 建立堆
        buildHeap();
        while (heapSize >= 2){
            // 将第一个元素与最后一个元素交换
            int tmp = data[heapSize - 1];
            data[heapSize - 1] = data[0];
            data[0] = tmp;
            // 堆大小-1
            heapSize --;
            // 从根节点调整堆，使其重新成为最大堆
            heap(0);
        }
    }
	
    public boolean add(E e) {
        return offer(e);
    }
    // 从这里可以看到，优先队列是不允许存在空元素的
    // 这个也比较好理解，空元素就无法进行比较了
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        // 如果长度大于队列长度，则进行动态增长
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        // 如果队列中没有元素，则直接放入队首
        if (i == 0)
            queue[0] = e;
        else // 否则，将其插入最后一个位置，并且进行堆的调整
            siftUp(i, e);
        return true;
    }

    // 动态增长
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // 如果容量小于64，则增长一倍，否则，增长1/2
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // 检查是否整数溢出
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }

    // 检查是否溢出
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    // 根据有无提供比较器选择不同的比较方法
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

    // 从这里可以看到，调整的方法为从位置k开始，查找其
    // 父节点的值，如果父节点的值比所要插入的值大，则进行交换，并且递归父节点
    // 也就是从二叉树树中"往上调整"
    // 否则，则不进行交换(最小堆嘛)
    private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }

    // 同上，只是这里使用默认的比较器
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

获得元素的索引

    private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10

删除元素

    public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }
    // 如果有相等的元素，则删除
    boolean removeEq(Object o) {
        for (int i = 0; i < size; i++) {
            if (o == queue[i]) {
                removeAt(i);
                return true;
            }
        }
        return false;
    }

    // 删除指定位置的元素
    private E removeAt(int i) {
        modCount++;
        int s = --size;
        if (s == i) // 删除最后一个元素
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            // 将所要删除的元素与最后一个元素交换
            // 并且向下调整
            siftDown(i, moved);
            // 如果发现没有进行调整，也就是说
            // 移动上来的最后一个节点比子孙节点的值都小
            // 此时需要向上进行调整，相当于插入一个新元素
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }

    // 删除元素，默认为第一个元素，也就是根元素
    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        // 将队首与队尾元素交换
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        // 调整堆
        if (s != 0)
            siftDown(0, x);
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

优先队列的本质其实就是一个最小堆，如果要使用最大优先队列，则需要传入自定义的比较器，在优先队列中，不需要存在空元素，并且要求传入优先队列中的元素必须是实现了Comparable接口

JAVA优先队列
package com.bbs.zebro.service;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueTester {
	public static void main(String[] args){
		Queue<Integer> pq = new PriorityQueue<Integer>(11);
		pq.add(1);
		pq.add(2);
		
		pq.add(3);
		pq.add(4);
		pq.add(5);
		pq.add(6);
		System.out.println(pq.poll().toString());//默认是小根堆 输出1
		Comparator<Integer> order =  new Comparator<Integer>(){
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				if(o1 < o2)
				{
					return 1;
				}
				else if(o1 > o2)
				{
					return -1;
				}
				else
				{
					return 0;
				}
			}
		};
		Queue<Integer> pq2 = new PriorityQueue<Integer>(11,order);
		pq2.add(1);
		pq2.add(2);
		pq2.add(3);
		pq2.add(4);
		pq2.add(5);
		System.out.println(pq2.poll().toString());//这么定义是大根堆 输出5
	}
}


C++
#include<iostream>
#include<string>
#include<vector>
#include<queue> 
#include<stdlib.h>
using namespace std;



int main(int argc,char** argv){
	priority_queue<int> pq;//等价于 priority_queue<int,vector<int>,less<int> > pq;
	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(4);
	pq.push(5);
	cout<<pq.top()<<endl;//默认是大根堆 输出5
	priority_queue<int,vector<int>,greater<int> > pq2; 
	pq2.push(1);
	pq2.push(2);
	pq2.push(3);
	pq2.push(4);
	pq2.push(5);
	cout<<pq2.top()<<endl;//此时是小根堆 输出1 
}


但是二者对于<号如果重载相同的意义,他们的表现是相同的.例如如果<都是表示本对象小于另外一个对象的比较结果,那么就是大根堆,否则就是小根堆.

使用结构体时注意在结构体里面重载相应的比较函数~~~.

/*
PriorityQueue中主要用到的就是Heap排序
*/
import java.util.PriorityQueue;

public class Main {
//队首为最大
static class Dog implements Comparable<Dog>{
private int num;
public Dog(int num){
this.num=num;
}
public int getNum(){
return this.num;
}
@Override
public int compareTo(Dog o) {
// TODO Auto-generated method stub
if(o.getNum()<=this.num)
return -1;
return 1;
}
}
//队首为最小
static class Cat implements Comparable<Cat>{
private int num;
public Cat(int num) {
// TODO Auto-generated constructor stub
this.num=num;
}
public int getNum(){
return this.num;
}
@Override
public int compareTo(Cat o) {
// TODO Auto-generated method stub
if(o.getNum()<=this.num)
return 1;
return -1;
}
}
public static void main(String[] args){
PriorityQueue<Dog> p0=new PriorityQueue<Dog>();
PriorityQueue<Cat> p1=new PriorityQueue<Cat>();
p1.offer(6);
p1.offer(0);
p1.offer(8);
p1.offer(7);
p1.offer(-2);
p0.offer(6);
p0.offer(0);
p0.offer(8);
p0.offer(7);
p0.offer(-2);
System.out.println(p0.poll());
System.out.println(p1.poll());
}

}