找兼职工作在家做哪个网站好,合肥关键词排名优化,中小型网站建设策划,wordpress 播放大视频播放优先级队列#xff08;堆#xff09;详解
目录
堆的概念堆的存储方式堆的基本操作优先级队列模拟实现PriorityQueue接口介绍堆排序Top-k问题
1、堆的概念
如果有一个关键码的集合K {k0#xff0c;k1#xff0c; k2#xff0c;…#xff0c;kn-1}#xff0c;把它的所…优先级队列堆详解
目录
堆的概念堆的存储方式堆的基本操作优先级队列模拟实现PriorityQueue接口介绍堆排序Top-k问题
1、堆的概念
如果有一个关键码的集合K {k0k1 k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中并满足Ki K2i1 且 Ki K2i2 (Ki K2i1 且 Ki K2i2) i 012…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 从堆的概念中不难看出堆实际上是一个特殊的完全二叉树。必须满足的条件是对于每一个根结点都小于它的孩子结点小堆或者每一个根节点都大于孩子结点大堆。 如下图
2、堆的存储方式
堆是一颗完全二叉树可以按照层序的规则采用顺序的方式进行存储。对于非完全二叉树在存储过程中会存储空结点浪费空间 将元素存储到数组中后可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标则有 如果i为0则i表示的节点为根节点否则i节点的双亲节点为 (i - 1)/2 如果2 * i 1 小于节点个数则节点i的左孩子下标为2 * i 1否则没有左孩子 如果2 * i 2 小于节点个数则节点i的右孩子下标为2 * i 2否则没有右孩子
3、堆的基本操作
1、向下调整
在讲堆的建立之前我们要了解一个非常重要的操作向下调整。 我们以建小根堆为例给定这样一个完全二叉树 我们要把它变成一个小根堆就要使用到向下调整的方法对于小根堆我们要保证每一个根结点都小于它的叶子结点如果有叶子结点。步骤如下
先从最初的根结点开始记为parent结点找到其左孩子结点数组下标2*parent1。判断有没有右孩子结点如果存在找到左右孩子中最小的孩子让child进行标记。将parent与较小的孩子child比较如果parent小于较小的孩子child调整结束。 否则交换parent与较小的孩子child交换完成之后parent中大的元素向下移动可能导致子树不满足对的性质因此需要继续向下调整即parent childchild parent*21。 然后重复这个过程。直到parent超出数组下标。 下图是向下调整的过程 向下调整的过程也是对于这颗树进行迭代比较而实现的。仔细思考一下我们发现向下调整的过程其实只影响改变了一条路径每次遇到孩子结点都有两种情况1、parent结点不需要和child结点互换调整直接结束。2、parent结点需要和child结点互换将child结点作为parent结点继续调整。不需要调整的部分原来就是符合堆的定义我们只是在这条路径上将最顶部的元素下调至相应位置这才是parent可以一条路走到黑的根本原因。接下来我们来看代码十分巧妙 public void shiftDown(int[] array, int parent) {int child 2*parent1;//左孩子结点while(childarray.length) {if(child1 array.lengtharray[child]array[child1]) {//先判断右孩子存不存在再找出两个孩子中的较大孩子child1;//child指向较大的孩子结点}if(array[parent]array[child]) {//比最大的孩子还大向下调整swap(array,parent,child);}else{break;}parent child;//继续向下调整child 2*parent1;}注意在调整以parent为根的二叉树时必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
2、堆的创建
对于一个普通序列根节点的左右子树不满足堆的特性我们又该如何调整呢 答案仍然是利用向下调整只不过我们要从下向上考虑。步骤如下
从后向前找到第一个不为叶子结点的结点记为root。从这个根结点向前遍历数组root–每遇到一个结点就向下调整一次直到走完数组root0。 直接上代码 public static void createHeap(int[] array) {int root (array.length-1-1)/2;//根据孩子结点求根结点for(;root0;root--) {shiftDown(array,root);}}3、堆的插入
堆的插入总共需要两个步骤
先将元素放入到底层空间中(注意空间不够时需要扩容)将最后新插入的节点向上调整直到满足堆的性质
这时我们所做的实际上是一种向上调整。仍然以小根堆为例下面是代码实现
public static void shiftUp(int[] array,int child) {int parent (child-1)/2;while(child0) {if(array[parent]array[child]) {swap(array,parent,child);}else{break;}child parent;parent (child-1)/2;}}比较向上调整与向下调整 1、向上调整是通过child结点去找parent结点而向下调整是通过parent结点去找child结点。 2、建堆的时候使用向下调整而不使用向上调整。因为向下调整操作的复杂度较低。
4、堆的删除
堆的删除一定删除的是堆顶元素。具体如下
将堆顶元素对堆中最后一个元素交换将堆中有效数据个数减少一个对堆顶元素进行向下调整
4、优先级队列模拟实现
前面介绍过队列队列是一种先进先出(FIFO)的数据结构但有些情况下操作的数据可能带有优先级一般出队列时可能需要优先级高的元素先出队列 在这种情况下数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。 我们接下来使用堆的操作模拟实现优先级队列直接上代码
import java.util.Arrays;public class PriorityQueue {public int[] array;public int usedSize;public static final int default_Capacity 10;//默认容量public PriorityQueue() {this.usedSize 0;this.array new int[default_Capacity];}/**** param array*/public void createHeap(int[] array) {int parent (array.length-2)/2;for(;parent0;parent--) {shiftDown(parent,usedSize);}}public static void swap (int[] array,int parent,int child) {int tmp array[parent];array[parent] array[child];array[child] tmp;}/**** param parent 是每棵子树的根节点的下标* param len 是每棵子树调整结束的结束条件* 向下调整的时间复杂度O(logn)*/private void shiftDown(int parent,int len) {int child 2*parent1;while(childlen) {if(child1lenarray[child]array[child1]) {child1;//child指向较大的孩子结点}if(array[parent]array[child]) {swap(array,parent,child);}else{break;}parent child;child 2*parent1;}}/*** 入队仍然要保持是大根堆* param val*/public void push(int val) {if(isFull()) {array Arrays.copyOf(array,2*array.length);}array[usedSize] val;usedSize;shiftUp(usedSize-1);}private void shiftUp(int child) {int parent (child-1)/2;while(child0) {if(array[parent]array[child]) {swap(array,parent,child);}else{break;}child parent;parent (child-1)/2;}}public boolean isFull() {return usedSize array.length;}/*** 出队【删除】每次删除的都是优先级高的元素* 仍然要保持是大根堆*/public int pollHeap() {int tmp array[0];swap(array,0,usedSize-1);usedSize--;shiftDown(0,usedSize);return tmp;}public boolean isEmpty() {return usedSize0;}/*** 获取堆顶元素* return*/public int peekHeap() {return array[0];}
}5、PriorityQueue接口介绍
三种构造器
PriorityQueue() 创建一个空的优先级队列默认容量是11PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列注意 initialCapacity不能小于1否则会抛IllegalArgumentException异常PriorityQueue(Collection?extends E c) 用一个集合来创建优先级队列
常用方法
booleanoffer(E e)插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常时间复杂度为Olog2N 注意空间不够时候会进行扩容E peek() 获取优先级最高的元素如果优先级队列为空返回nullE poll() 移除优先级最高的元素并返回如果优先级队列为空返回nullint size() 获取有效元素的个数void clear() 清空队列boolean isEmpty() 检测优先级队列是否为空空返回true
6、堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤
建堆 升序建大堆 降序建小堆利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。 public void heapSort() {int end usedSize-1;while (end 0) {swap(0,end);siftDown(0,end-1);end--;}7、Top-k问题堆排序的应用
TOP-K问题即求数据集合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 基本思路如下
用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
//使用比较器创建小根堆
class LessIntComp implements ComparatorInteger { Overridepublic int compare(Integer o1, Integer o2) { return o1 - o2; }}
//使用比较器创建大根堆
class GreaterIntComp implements ComparatorInteger{ Overridepublic int compare(Integer o1, Integer o2) { return o2 - o1; }
}
public class TestDemoE { //求最小的K个数通过比较器创建大根堆public static int[] smallestK(int[] array, int k) { if(k 0) { return new int[k]; }GreaterIntComp greaterCmp new GreaterIntComp(); PriorityQueueInteger maxHeap new PriorityQueue(greaterCmp); //先将前K个元素创建大根堆 for(int i 0; i k; i) {maxHeap.offer(array[i]); }//从第K1个元素开始每次和堆顶元素比较 for (int i k; i array.length; i) { int top maxHeap.peek(); if(array[i] top) {maxHeap.poll();maxHeap.offer(array[i]); } }//取出前K个int[] ret new int[k]; for (int i 0; i k; i) { int val maxHeap.poll(); ret[i] val;}return ret;
}
