自己开网站能赚钱吗,宇宙设计网站推荐,网站建设代理,做网站推广的是什么职位文章目录 前言优先级队列 PriorityQueue优先队列的模拟实现 堆堆的储存方式堆的创建建堆的时间复杂度堆的插入与删除 总结 前言 优先级队列 PriorityQueue
概念#xff1a;对列是先进先出的的数据结构#xff0c;但有些情况#xff0c;数据可能带有优先级#xff0c;一般出… 文章目录 前言优先级队列 PriorityQueue优先队列的模拟实现 堆堆的储存方式堆的创建建堆的时间复杂度堆的插入与删除 总结 前言 优先级队列 PriorityQueue
概念对列是先进先出的的数据结构但有些情况数据可能带有优先级一般出队列时可能需要优先级高的元素先出队列。所以像这种情况用队列不太合适在手机上玩游戏时如果有来电系统应该优先处理打进来的电话。以前是来电显示充满整个画面现在变成了一个小窗。
优先队列的模拟实现
PriorityQueue的底层使用了堆这种数据结构PriorityQueue底层实现是一个完全二叉树完全二叉树又分为大根堆和小根堆
堆
概念 小根堆根节点比左右孩子都小。只考虑根和左右节点的关系不考虑左右节点的哪个大。 大根堆根节点比左右孩子都大
堆的储存方式 将元素存储到数组中后可以根据二叉树章节的性质5对树进行还原。假设为节点在数组中的下标则有: 如果为0则表示的节点为根节点否则节点的双亲节点为(i 1)/2 ●如果2i 1小于节点个数则节点的左孩子下标为2 门中1,否则没有左孩了 ●如果2i2小于节点个数则节点的右孩子下标为21 2,否则没有右孩子
堆的创建
让parent标记需要调整的节点child标记parent的左孩子(注意: parent如果有孩子一 定先是有左孩子)如果parent的左孩子存在即:child size,进行以下操作 直到parent的左孩子不存在 parent右孩子是否存在存在找到左右孩子中最大的孩子让child进行标记将parent 与较大的孩子child比较,如果: parent小于较大的孩子child,交换parent与较大的孩子child,交换完成之后parent中小的元素向下移动并继续向下调整即parent child; child parent*21;然后继续 否则:退出循环。
public class TestHeap {//创建一个数组public int[] elem;public int useSize;//有效元素//构造方法给elem分配内存public TestHeap() {this.elem new int[10];}//初始化elem数组给elem传入元素public void initElem(int[] array){for (int i 0; i array.length; i) {elem[i] array[i];useSize;}}/*** 创建大根堆的代码*/public void createHeap(){for (int parent (useSize-1-1)/2 ; parent 0 ; parent--) {siftDown(parent,useSize);}}/*** 向下调整* param parent* param len*///让child标记根的左孩子如果左孩子大于数组长度则进行下面操作// 如果右孩子小于长度并且左孩子的值小于右孩子的值让左孩子移到右孩子上private void siftDown(int parent,int len){int child 2*parent1;while(child len){if (child1 len elem[child] elem[child1]){child child1;}//此时child保存的是孩子节点中最大的值//如果左孩子大于根节点两者的值交换。if (elem[child] elem[parent]) {//和根节点交换int tmp elem[child];elem[child] elem[parent];elem[parent] tmp;//交换完再换位置parent child;//根节点移到孩子节点上child 2*parent1;//孩子节点再往下移}else{break;}}}
}public class Test {public static void main(String[] args) {TestHeap testHeap new TestHeap();int[] array{27,15,19,18,28,34,65,49,25,37};testHeap.initElem(array);testHeap.createHeap();System.out.println();}
}建堆的时间复杂度 因此建堆的时间复杂度是0N
堆的插入与删除
堆的插入 private void swap(int i,int j){int tmp elem[i];elem[i] elem[j];elem[j] tmp;}//向上调整public void push(int val){if(isFull()){elem Arrays.copyOf(elem,elem.length*2);}elem[usedSize] val;siftUp(usedSize);usedSize;}public boolean isFull(){return usedSize elem.length;}public void siftUp(int child){int parent (child-1)/2;while(child 0){if (elem[child] parent){swap(child,parent);child parent;parent (child-1)/2;}else{break;}}}堆的删除 注意这里的删除指的是删除堆顶的元素
将0下标的的堆顶元素和堆的最后一个元素交换将堆的有效个数usedSize–对堆进行向下调整 //删除堆顶元素public int pop(){if (empty()){return -1;}int oldVal elem[0];swap(0,usedSize-1);usedSize--;siftDown(0,usedSize);return oldVal;}public boolean empty(){return usedSize 0;}总结
本章节学习如何实现一个堆如何运用到向上调整向下调整。
