1: 与前面说的最小优先队列相反
堆的排序也相反 :
package com.algorithm.common; import java.util.Iterator; import java.util.NoSuchElementException; /** * 大顶堆排序 最大优先队列 * @author lijunqing */ public class MaxPQ<Key> implements Iterable<Key> { private int N; private Key[] pq; public MaxPQ() { this(1); N=0; } public MaxPQ(int initCapacity) { pq=(Key[])new Object[initCapacity + 1]; N=0; } /** * 添加一个到堆中 * @param key */ public void insert(Key key) { if(N == pq.length - 1) { // 申请2培空间 resize(2 * pq.length); } N++; pq[N]=key; swim(N); } /** * 递归调整当前节点和父节点的 * @param n2 */ private void swim(int i) { while(i > 1 && greater(i, i / 2)) { exch(i, i / 2); i=i / 2; } } /** * 堆顶出堆 重新调整堆 * @return */ public Key delMax() { exch(1, N); Key max=pq[N]; pq[N]=null; N--; skin(1); return max; } /** * 从i节点开始调整堆 * @param i */ private void skin(int i) { while(2 * i <= N) { int k=2 * i; if(k < N && greater(k+1, k)) { k++; } if(greater(i, k)){ break; } exch(i, k); i=k; } } /** * i节点大于j节点 * @param i * @param i2 * @return */ private boolean greater(int i, int j) { return ((Comparable<Key>)pq[i]).compareTo(pq[j]) > 0; } /** * 重新申请空间 * @param capacity */ private void resize(int capacity) { Key[] temp=(Key[])new Object[capacity]; for(int i=0; i < pq.length; i++) { temp[i]=pq[i]; } pq=temp; } /** * 交互节点值 * @param i * @param j */ private void exch(int i, int j) { Key temp=pq[i]; pq[i]=pq[j]; pq[j]=temp; } public int size() { return N; } public boolean isEmpty() { return N == 0; } @Override public Iterator<Key> iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator<Key> { // 重新建一个 private MaxPQ<Key> copy; public HeapIterator() { copy=new MaxPQ<Key>(size()); for(int i=1; i <= N; i++) copy.insert(pq[i]); } public boolean hasNext() { return !copy.isEmpty(); } public void remove() { throw new UnsupportedOperationException(); } public Key next() { if(!hasNext()) throw new NoSuchElementException(); return copy.delMax(); } } public static void main(String[] agrs) { MaxPQ<Integer> max=new MaxPQ<Integer>(); max.insert(22); max.insert(1); max.insert(56); max.insert(41); max.insert(3); max.insert(27); Iterator<Integer> m = max.iterator(); while(m.hasNext()){ System.out.println(m.next()); } } }
结果:
56 41 27 22 3 1
相关推荐
编写优先队列数据(priority_queue)类型,优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先...对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素。
本程序主要由堆来实现优先队列的数据结构,主要有优先队列的删除,插入。算法复杂度为logn
利用优先队列(大顶堆)解决轮廓线问题,广东工业大学教程,还不错的
用C语言实现一个优先队列;压缩文件中包括三个文件:1.HeapQueue.h优先队列源代码,2.main.cpp测试主函数;3.HeapQueue.h使用说明
优先队列有两种常见的类型:最大优先队列和最小优先队列。在最大优先队列中,优先级最高的元素(即值最大的元素)最先出队;而在最小优先队列中,优先级最低的元素(即值最小的元素)最先出队。如果队列中有多个元素...
优先队列的数据结构是由大顶堆来实现的,每次优先输出最大优先权值。 有搜索优先权最大的值、插入元素值、删除最大优先权值三个主要操作。
优先队列,问题关于费用的最大优先队列,优先队列,C语言数据结构课程设计,堆,简单易懂
链队列题目:初始化队列+入队列+出队列+销毁队列
使用最大堆实现最大优先队列,采用顺序存储,仅供学习交流
构建最大堆,维护最大堆,堆排序,以及对在优先队列中的应用。对最大优先队列执行以下操作:向队列中插入新元素,增加某个元素的值,去掉并返回队列中的最大值并保证最大队的性质
2)若尾指针rear小于队列的最大下标maxSize-1,则将数据存入rear所指的数中组元素中,否则无法存入数据。rear==maxSize-1[队列满] 环形队列 1)front变量的含义做一个调整:front就指向队列的第一个元素,也就是说...
查询最大优先队列的元素,和最小优先队列的元素,时间复杂度为o(1) 因为数组的第一个元素便是我们所需要得要的元素。 而插入操作,只要判断应该插入那棵树,也将是O(1),然而之后需要调整,此时的时间...
两部分代码:静态空间与动态空间实现堆的各种操作,以及利用这些操作实现最大优先队列的vc源码。其中算法思想主要是依据《算法导论》堆的介绍,以及表的扩张与收缩章节内容(动态部分)
数据结构,课程设计优先队列实验报告 用最大堆实现的优先队列
优先队列-java可以选择属性和升序降序
可嵌入到matlab中的优先队列,包括pq_create,插入,删去,取顶端,
优先队列.rar 优先队列.rar 优先队列.rar 优先队列.rar
本文实例为大家分享了python实现最大优先队列的具体代码,供大家参考,具体内容如下 说明:为了增强可复用性,设计了两个类,Heap类和PriorityQ类,其中PriorityQ类继承Heap类,从而达到基于最大堆实现最大优先队列...
C语言 堆 优先队列
堆排序实现优先队列,利用优先队列做了一个小程序,有兴趣看看