java中优先级队列,java的优先级队列使用方法

　　00-1010 1.二叉树的顺序存储1.1存储方式1.2下标关系2。堆)2.1概念2.2操作-(下沉和浮动)这个例子是最大堆2.3构建堆-完整代码(最大堆)3。优先队列

1. 二叉树的顺序存储

　　00-1010 1.堆在逻辑上是一棵完整的二叉树。

　　2.堆物理上存储在一个数组中。

　　3.满足任一节点的值大于其子树中节点的值，称为大堆、大根堆或最大堆。

　　4.反之，就是小堆，或者小根堆，或者最小堆。

　　5.堆的基本功能是快速找到集合中的最高值。

　　00-1010元件下沉：

　　/* * * sinking操作*/public void siftDown(int k){ //还有一个子树while(left child(k)data . size()){ int j=left child(k)；//判断是否有右子树以及值if是否大于左子树(j 1 data . size()data . get(J1)data . get(j)){ j=J1；}//此时j是左右子树的最大值//和当前节点的比较大小if(data . get(j)=data . get(k)){ break；}else { swap(k，j)；k=j；}}}元素浮动：

　　/* * *浮点运算*//浮点运算的结束条件：已到达根节点当前节点值=父节点值//循环的迭代条件3360仍存在且当前节点值父节点值private void sift up(int k){ while(k 0 data . get(k)data . get(parent(k))k=parent(k)；}}如果交换方法是交换操作：

　　//exchange triple private void swap(int I，int j){ int temp=data . get(j)；data.set(j，data . get(I))；data.set(i，temp)；}堆数组：

　　/* * * Heap any array * @ param arr */PublicMaxHeap(int[]arr){ data=NewArrayList(arr . length)；//1.先将arr的所有元素复制到(int i : arr){ data.add(i)的数据数组中；} //2.从最后一个非叶节点开始向下筛选for(int I=parent(data . size()-1)；I=0；我- ) {

　　 siftDown(i); } }图示：

　　以此数组为例：

// 调整前int[] array = { 27,15,19,18,28,34,65,49,25,37 };// 调整后int[] array = { 15,18,19,25,28,34,65,49,27,37 };

　　时间复杂度分析：

　　最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度

　　即时间复杂度为 O(log(n))

2.3 建堆-完整代码（最大堆）

/** * 基于整形最大堆实现 * 时根节点从0开始编号,若此时节点编号为k * 左孩子为2k+1 * 右孩子为2k+2 * 父节点为（k-1）/2 */ import java.util.ArrayList;import java.util.List;import java.util.NoSuchElementException; public class MaxHeap { // 使用JDK的动态数组(ArrayList)来存储一个最大堆 List<Integer> data; // 构造方法的this调用 public MaxHeap(){ this(10); } // 初始化的堆大小 public MaxHeap(int size){ data = new ArrayList<>(size); } /** * 将任意数组堆化 * @param arr */ public MaxHeap(int[] arr){ data = new ArrayList<>(arr.length); // 1.先将arr的所有元素复制到data数组中 for(int i : arr){ data.add(i); } // 2.从最后一个非叶子结点开始进行siftDown for (int i = parent(data.size()-1); i >=0 ; i--) { siftDown(i); } } /** * 向最大堆中增加值为Value的元素 * @param value */ public void add(int value){ //1.先直接加到堆的末尾 data.add(value); //2.元素上浮操作 siftUp(data.size()-1); } /** * 只找到堆顶元素值 * @return */ public int peekMax (){ if(isEmpty()){ throw new NoSuchElementException("heap is empty!connot peek"); } return data.get(0); } /** * 取出当前最大堆的最大值 */ public int extractMax(){ // 取值一定注意判空 if(isEmpty()){ throw new NoSuchElementException("heap is empty!connot extract"); } int max = data.get(0); // 1.将数组末尾元素顶到堆顶 int lastValue =data.get(data.size()-1); data.set(0,lastValue); // 2.将数组末尾的元素删除 data.remove(data.size()-1); // 3.进行元素的下沉操作 siftDown(0); return max; } /** * 下沉操作 */ public void siftDown(int k){ //还存在子树 while (leftChild(k) < data.size()){ int j = leftChild(k); //判断是否存在右子树且大于左子树的值 if(j+1 < data.size() && data.get(j+1) > data.get(j)){ j=j+1; } //此时j为左右子树最大值 //和当前节点比较大小 if(data.get(j) <= data.get(k)){ break; }else { swap(k,j); k=j; } } } /** * 上浮操作 */ // 上浮操作的终止条件: 已经走到根节点 当前节点值 <= 父节点值 // 循环的迭代条件 : 还存在父节点并且当前节点值 > 父节点值 private void siftUp(int k) { while (k>0 && data.get(k)>data.get(parent(k))){ swap(k,parent(k)); k=parent(k); } } //交换三连 private void swap(int i,int j) { int temp = data.get(j); data.set(j,data.get(i)); data.set(i,temp); } //判读堆为空 public boolean isEmpty(){ return data.size() == 0; } //根据索引找父节点 public int parent(int k){ return (k-1)>>1; } //根据索引找左孩子 public int leftChild(int k){ return k<<2+1; } //根据索引找右孩子 public int rightChild(int k){ return k<<2+2; } @Override public String toString() { return data.toString(); }}

ps:随机数操作

 int[] data=new int[10000]; //随机数 ThreadLocalRandom random = ThreadLocalRandom.current(); for (int i = 0; i < data.length; i++) { data[i] = random.nextInt(); }

3. 优先级队列

详见下节：Java堆&优先级队列示例讲解(下)

　　到此这篇关于Java堆&优先级队列示例讲解(上)的文章就介绍到这了,更多相关Java 堆优先级队列内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

java中优先级队列,java的优先级队列使用方法_1

目录

1. 二叉树的顺序存储

2.3 建堆-完整代码（最大堆）

3. 优先级队列

相关文章阅读