腾龙官方网站做号软件,wordpress 电商 开发,自助网站建设开发流程步骤,wordpress 禁止目录浏览文章目录 优先级队列堆堆的概念堆的模拟实现创建堆入堆判满删除判空获取栈顶元素 创建堆两种方式的时间复杂度堆排序java提供的PriorityQueue类基本的属性关于PriorityQueue类的三个构造方法关于PriorityQueue类中#xff0c;入堆方法是怎样实现的#xff1f;PriorityQueue注… 文章目录 优先级队列堆堆的概念堆的模拟实现创建堆入堆判满删除判空获取栈顶元素 创建堆两种方式的时间复杂度堆排序java提供的PriorityQueue类基本的属性关于PriorityQueue类的三个构造方法关于PriorityQueue类中入堆方法是怎样实现的PriorityQueue注意事项 堆的一个oj题 优先级队列
前面介绍过队列队列是一种先进先出(FIFO)的数据结构但有些情况下操作的数据可能带有优先级一般出队列时可能需要优先级高的元素先出队列该种场景下使用队列显然不合适比如在手机上玩游戏的时候如果有来电那么系统应该优先处理打进来的电话初中那会班主任排座位时可能会让成绩好的同学先挑座位。在这种情况下数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
堆
优先级队列是一种概念的数据结构我们使用堆这种具体的数据结构来实现它。
堆的概念
堆是一棵以数组方式存储的完全二叉树。 存储方式按照层序遍历的方式存储。
堆又分为小根堆大根堆两种 大根堆是指所有的节点值比其左右节点值都大左右节点在的情况下。 大根堆的根节点是最大值 小根堆是指所有的节点指比其左右节点值都小左右节点在的情况下。 小根堆的根节点是最小值
堆的模拟实现
我们以大根堆举例 实现的方法与属性
public class PriorityQueue {public int[] elem;public int usedSize;//初始化长度为10的数组public PriorityQueue() {elem new int[10];}//创建建堆public void createHeap(int[] array) {}private void shiftDown(int root,int len) {}// 入堆仍然要保持是大根堆public void push(int val) {}private void shiftUp(int child) {}//判断堆是否满public boolean isFull() {}//每次删除的都是优先级高的元素,删除后任是大根堆public void pollHeap() {}//判断堆是否为空public boolean isEmpty() {}// 获取堆顶元素public int peekHeap() {}
}创建堆
创建堆的方式有两种一种是向上调整向下调整。 我们依次介绍 向下调整根据一组数据创建成一个大根堆以{153876}举例 所以向下调整的含义即每一棵子树均从根节点开始向下比较。实现思想
createHeap思路
先将数组拷贝进成员数组中注意看长度是否够。 我们从最后一棵子树的根节点开始调用shiftDown方法向上一棵一棵树的调整为大根堆。 2. shiftDown思路
将当前传入的根节点与他的孩子节点将最大值选出作为根。 然后将根变成孩子节点再次调整。 注意挑选最大值的时候要判断不能让下标越界。
public void createHeap(int[] array) {if(elem.length array.length){elem Arrays.copyOf(elem, elem.length * 2);}for (int i 0; i array.length; i){elem[i] array[i];usedSize;}for (int root (usedSize -1 -1) / 2; root 0 ; root--) {siftDown(root,usedSize);}}private void siftDown(int root,int len) {int child root * 2 1;while (child len){//寻找孩子节点的大值if(child 1 len elem[child] elem[child 1]){child;}if(elem[root] elem[child]){swap(elem,root,child);root child;child root * 2 1;}else {break;}}}//交换函数private void swap(int[] array,int x,int y){int tmp array[x];array[x] array[y];array[y] tmp;}向上调整 向上调整的思路即以入堆的方式将每一个元素依次插入堆中。 我们从最后一棵节点开始于其子树的根节点比较这个向上比较的过程我们称为向上调整。代码实现
public class Test {public static void main(String[] args) {int [] array {27,15,19,18,28,34,65,49,25,37};TestHeap testHeap new TestHeap();for (int i 0; i array.length; i) {testHeap.push(array[i]);}}
} 具体的入堆代码看下面。入堆 代码思路
先判断堆是否已经满了满了要扩容。在堆最后存入该元素然后与父亲节点相比较比父亲节点大就交换直到到根节点或者比父亲节点小为止。
public void push(int val) {if(isFull()){elem Arrays.copyOf(elem, elem.length*2);}elem[usedSize] val;siftUp(usedSize);usedSize;}private void siftUp(int child) {int parent (child - 1) / 2;while(parent 0) {if (elem[parent] elem[child]) {swap(elem, parent, child);child parent;parent (child - 1) / 2;}else {break;}}}判满
public boolean isFull() {return usedSize elem.length;}删除 实现思想
先判断堆是否为空为空直抛空指针异常。我们先将堆顶和堆尾交换然后向下调整一次。usedSize减1。
public void pollHeap() throws NullPointerException {if (isEmpty()) {throw new NullPointerException();}swap(elem,0,usedSize-1);siftDown(0,usedSize);usedSize--;}判空
public boolean isEmpty() {return usedSize 0;}获取栈顶元素
如果堆为空抛空指针异常没有直接返回堆顶元素。
public int peekHeap() throws NullPointerException {if (isEmpty()) {throw new NullPointerException();}return elem[0];}创建堆两种方式的时间复杂度
向下调整的时间复杂度为ON 当计算复杂度时只计算替换次数即可不需要计算每次替换中语句的执行数目因为到最后计算时前面的系数均会变为1. 向上调整的时间复杂度为O(N*logN)
堆排序
假设我们要将一组数据在一个数组中从小到大排序那我们要创建大根堆还是小根堆 如果要创建小根堆我们只能保证堆顶元素为最小值但是不能保证左边的元素比右边的元素大这不是小根堆的特性。 所以我们要创建大根堆
public void heapsort(){
//此方法是在创建大根堆之后的堆排序方法int end Usedsize-1;while(end0){swap(elem,0,end);siftDown(0,end);end--; }
}java提供的PriorityQueue类
基本的属性 DEFAULT_INITIAL_CAPACITY 为申请初始化空间大小的默认值queue为底层使用的数组size指数组中有效元素的个数comparator指类使用的比较器
关于PriorityQueue类的三个构造方法 这三个构造方法均调用了自己的第四个构造方法
所以我们直接看第四个构造方法实现逻辑如果申请的空间大小小于1则直接报异常当大于等于1时为优先级队列申请第一个参数数值大小的空间并采用第二个参数的比较器。
关于PriorityQueue类中入堆方法是怎样实现的 PriorityQueue注意事项
PriorityQueue中放置的元素必须是可以比较的即实现了comparable接口的类,否则会报ClassCastException异常。不能插入null对象否则会报NullPointerException异常。没有容量限制可以插入任意多个元素其内部可以自动扩容。
堆的一个oj题
Topk问题最小的k个数 这个题有三种做法 直接进行整体堆排序。 直接建立一个小根堆然后依次出堆顶元素再调整 把前k个元素创建为大根堆遍历剩下的N-K个元素和栈顶元素比较如果比栈顶元素小则删除栈顶元素将此元素入堆。 此种算法的时间复杂度为前k个元素创建一个大根堆的时间复杂度加上后面N-k个元素进行入堆操作的时间复杂度klogk(N-k)*logk Nlogk 采用第三种做法
class Clmp implements ComparatorInteger{Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
class Solution {public int[] smallestK(int[] arr, int k) {int [] ret new int[k];if(arr null||k0){return ret;}PriorityQueueIntegerpriorityQueue new PriorityQueue(k,new Clmp());//我们需要创建一个大根堆//将前k个元素插入到优先级队列中去for (int i 0; i k; i) {priorityQueue.offer(arr[i]);}
//然后遍历剩余的元素for (int i k; i arr.length ; i) {if(arr[i] priorityQueue.peek()) {//则将两者的值进行交换priorityQueue.poll();priorityQueue.offer(arr[i]);}}ret new int[k];for (int i 0; i k; i) {ret[i] priorityQueue.poll();}return ret;}
}
