java 优先队列,优先级队列采用什么数据结构

　　00-1010一、堆的概念二。向下调整1。构建初始堆II。建造第三堆。优先级队列1。什么是优先级队列？2.三号队列。四号队列。返回到队列5的第一个元素。堆中其他TopK问题的摘要：摘要

　　00-1010堆的定义：n个元素的序列{k1，k2，…，kn}称为堆当且仅当满足以下条件：

　　(1)大根桩用1)ki=k2i和ki=k(2i 1) ——

　　(ki=K2I且ki=k(2i 1) ——的小根堆

　　简单来说：

　　堆是一个完整的二叉树，具有以下性质：(1)每个节点的值大于或等于其左右子节点的值，称为大根堆(如左下图所示)；或者：(1)每个节点的值小于或等于其左右子节点的值，称为小根堆(如下图右图所示)。

　　我们用数组来保存二叉树结构，也就是我们通过序列遍历把二叉树放入数组，如上图所示。

　　堆的元素下标具有以下关系：

　　1.如果父节点的下标是已知的，那么

　　Child (left)下标=2parent1

　　子(右)下标=2parent2

　　2.如果子(左和右)下标已知，则：

　　父下标=(子-1)/2；

　　总结：

　　堆在逻辑上是一棵完整的二叉树；堆在物理上存储在数组中；满足任一节点的值大于其子树中节点的值，称为大堆、大根堆或最大堆；反之，就是小堆，或者小根堆，或者最小堆；堆的基本功能是快速找到一个集合中的最大值。

　　public static void shift down(int[]array，int size，int index){ int left=2 * index 1；while(left size){ int min=left；int right=2 * index 2if(right size){ if(array[right]array[left]){ min=right；} } if(array[index]=array[min]){ break；} int tmp=array[index]；数组[索引]=数组[最小值]；array[min]=tmp；index=min左=2 *索引1；

　　 } }时间复杂度为 O(log(n))。

2.建堆

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

　　时间复杂度分析：

　　粗略估算，可以认为是在循环中执行向下调整，为 O(n * log(n))，（了解）实际上是 O(n)。

//建堆代码 public void createHeap(int[] array) { for (int i = 0; i < array.length; i++) { elem[i] = array[i]; usedSize++; } //根据代码 显示的时间复杂度 看起来 应该是O(n*logn) 但是 实际上是O(n) for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) { //调整 shiftDown(parent,usedSize); } }

三、优先级队列

1.什么是优先队列？

根据百科解释：

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（first in, largest out）的行为特征。通常采用堆数据结构来实现。

　　

所以我们在这里实现优先队列的内部原理是堆，也就是说采用堆来构建。

2.入队列

过程（以大堆为例）：

　　首先按尾插方式放入数组；比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束；否则，交换其和双亲位置的值，重新进行 2、3 步骤；直到根结点。下面图解：

 private void shiftUp(int child) { int parent = (child-1)/2; while (child > 0) { if(elem[child] > elem[parent]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; child = parent; parent = (child-1)/2; }else { break; } } }

3.出队列

为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向下调整方式重新调整成堆。

　　

 private void shiftUp(int child) { int parent = (child-1)/2; while (child > 0) { if(elem[child] > elem[parent]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; child = parent; parent = (child-1)/2; }else { break; } } } public void offer(int val) { if(isFull()) { //扩容 elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize++] = val; //注意这里传入的是usedSize-1 shiftUp(usedSize-1); }

4.返回队首元素

直接返回堆顶元素

 public int peek() { if(isEmpty()) { throw new RuntimeException("优先级队列为空！"); } return elem[0]; } public boolean isEmpty() { return usedSize == 0; }

整体的代码：

public class TestHeap { public int[] elem; public int usedSize; public TestHeap() { this.elem = new int[10]; } /** * 向下调整函数的实现 * @param parent 每棵树的根节点 * @param len 每棵树的调整的结束位置 10 */ public void shiftDown(int parent,int len) { int child = 2*parent+1; //1、最起码 是有左孩子的，至少有1个孩子 while (child < len) { if(child+1 < len && elem[child] < elem[child+1]) { child++;//保证当前左右孩子最大值的下标 } if(elem[child] > elem[parent]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; parent = child; child = 2*parent+1; }else { break; } } } public void createHeap(int[] array) { for (int i = 0; i < array.length; i++) { elem[i] = array[i]; usedSize++; } //根据代码 显示的时间复杂度 看起来 应该是O(n*logn) 但是 实际上是O(n) for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) { //调整 shiftDown(parent,usedSize); } } private void shiftUp(int child) { int parent = (child-1)/2; while (child > 0) { if(elem[child] > elem[parent]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; child = parent; parent = (child-1)/2; }else { break; } } } public void offer(int val) { if(isFull()) { //扩容 elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize++] = val; //注意这里传入的是usedSize-1 shiftUp(usedSize-1); } public boolean isFull() { return usedSize == elem.length; } public int poll() { if(isEmpty()) { throw new RuntimeException("优先级队列为空！"); } int tmp = elem[0]; elem[0] = elem[usedSize-1]; elem[usedSize-1] = tmp; usedSize--; shiftDown(0,usedSize); return tmp; } public int peek() { if(isEmpty()) { throw new RuntimeException("优先级队列为空！"); } return elem[0]; } public boolean isEmpty() { return usedSize == 0; } public void heapSort() { int end = this.usedSize-1; while (end > 0) { int tmp = elem[0]; elem[0] = elem[end]; elem[end] = tmp; shiftDown(0,end); end--; } }}

5.堆的其他TopK问题

什么是TopK问题？

　　从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题。

　　解决这类问题，我们往往会有以下几种思路：

　　对整体进行排序，输出前10个最大的元素。用上面刚刚讲的堆。也是用堆，不过这比第二个思路更巧妙。我们直接讲思路三：

　　先用前k个元素生成一个小顶堆，这个小顶堆用于存储，当前最大的k个元素。接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。直到，扫描完所有n-k个元素，最终堆中的k个元素，就是所要求的TopK。以这个数组{12，15，21，41，30}为例，找到前3个最大的元素。

　　那如果是将一组进行从小到大排序，我们该采用大根堆还是小根堆？

　　答案是：大根堆！

　　步骤如下：

　　将这组数据调整为大根堆调整为大根堆；0下标和最后1个未排序的元素进行交换即可；重复1、2，直到结束。

总结：

如果求前K个最大的元素，要建一个小根堆。如果求前K个最小的元素，要建一个大根堆。第K大的元素。建一个小堆，堆顶元素就是第K大的元素。第K小的元素。建一个大堆，堆顶元素就是第K小的元素。

 public void heapSort() { int end = this.usedSize-1; while (end > 0) { int tmp = elem[0]; elem[0] = elem[end]; elem[end] = tmp; shiftDown(0,end); end--; } } public void shiftDown(int parent,int len) { int child = 2*parent+1; //1、最起码 是有左孩子的，至少有1个孩子 while (child < len) { if(child+1 < len && elem[child] < elem[child+1]) { child++;//保证当前左右孩子最大值的下标 } if(elem[child] > elem[parent]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; parent = child; child = 2*parent+1; }else { break; } } }

总结

来来回回，这篇文章写了2-3天了，以前写文章总是蜻蜓点水，不到水深，导致自己对很多的知识也没有多深理解，仅仅是为了写文章而写文章。希望有改变，从这篇文章开始吧！

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

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