模板网建站网站建设证书

当前位置： 首页 > news >正文

模板网建站,网站建设证书,模板 网站,网站主页设计费用优先级队列—-堆优先级队列堆堆的创建堆的插入#xff1a;堆的删除#xff1a;PriorityQueue的特性PriorityQueue的构造与方法优先级队列 优先级队列#xff1a; 不同于先进先出的普通队列#xff0c;在一些情况下#xff0c;优先级高的元素要先出队列。而这种队列需要提… 优先级队列—-堆优先级队列堆堆的创建堆的插入堆的删除PriorityQueue的特性PriorityQueue的构造与方法优先级队列 优先级队列 不同于先进先出的普通队列在一些情况下优先级高的元素要先出队列。而这种队列需要提供两个基本的操作返回最高优先级对象 和 添加新的对象。 JDK1.8中优先级队列底层使用的是 堆 数据结构而堆则是在完全二叉树的基础上进行了调整 堆 堆 将一组集合的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足Ki K2i1 且 Ki K2i2 为 小堆Ki K2i1 且 Ki K2i2 为 大堆。i 012…将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。例如 堆的两个性质 堆中某个结点的值总是不大于或不小于其父节点的值。 堆总是一棵完全二叉树。 堆的存储方式 堆是一棵完全二叉树因此可以用层序的规则采用顺序的方式来高效存储但对于非完全二叉树就不适合使用顺序方式进行存储因为为了能够还原二叉树空间中必须要存储空节 点就会导致空间利用率比较低。 如果 i 表示孩子结点则父节点为 (i - 1)/2。 如果 i 表示根结点左孩子则为 2i 1右孩子为 2i 2。 堆的创建 向下调整过程以小根堆为例 让 parent 标记需要调整的节点child 标记 parent 的左孩子完全二叉树中一定先有左孩子如果 parent 的左孩子存在child size进行以下操作直到 parent 的左孩子不存在 找到左右孩子中较小的结点和 parent 进行比较若 parent 小则调整结束。若 parent 大则进行交换。交换后可能会使原来满足堆的子树发生改变所以需要继续向下调整。 例如 代码 public class TestHeap {public int[] elem;public int usedSize;public TestHeap() {this.elem new int[10];}//初始化public void initElem(int[] array) {for (int i 0; i array.length; i) {elem[i] array[i];usedSize;}}public void createHeap() {//循环调用for (int parent (usedSize - 1 - 1) / 2; parent 0; parent–) {shiftDown(parent, usedSize);}}//向下调整 len为当前有效数据个数private void shiftDown(int parent, int len) {int child 2 * parent 1;//最起码 要有左孩子while (child len) {//一定是有右孩子的情况下if (child 1 len elem[child] elem[child 1]) {//保证 child指向较小值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 offer(int val) {if (isFull()) {//满了扩容elem Arrays.copyOf(elem, 2 * elem.length);}//放到最后一个位置长度加一elem[usedSize] val;//向上调整shiftUp(usedSize-1);}public boolean isFull() {return usedSize elem.length;}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 pop() {if (isEmpty()) {return;}//交换int tmp elem[0];elem[0] elem[usedSize - 1];elem[usedSize - 1] tmp;//有效数据个数减一usedSize–;//向下调整shiftDown(0, usedSize);}public boolean isEmpty() {return usedSize 0;}PriorityQueue的特性 Java 集合框架中提供了 PriorityQueue 和 PriorityBlockingQueue 两种类型的优先级队列PriorityQueue 是线程不安全的PriorityBlockingQueue 是线程安全的这里主要介绍PriorityQueue。 使用 PriorityQueue 需要注意 使用时必须导入 PriorityQueue 所在的包(import java.util.PriorityQueue;)。 PriorityQueue 中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出 ClassCastException 异常。 只插入一个元素时并不会报错 插入多个元素就会报错 不能插入 null 对象否则会抛出 NullPointerException。 内部可以自动扩容。 插入和删除元素的时间复杂度为 O(log₂N)。 PriorityQueue 底层使用的是堆数据结构。 PriorityQueue 默认情况下是小堆。
PriorityQueue的构造与方法 PriorityQueue 的几种构造方法
PriorityQueue 的方法 PriorityQueue 的方法和其它数据结构类似 Top-k 问题 最大或者最小的前k个数据。例如求一组数据中前 k 个最小的数据。 题目链接leetcode—-面试题 17.14. 最小K个数 题目描述 思路一我们可以初始化一个数组大小的堆然后遍历数组的同时将元素放进堆中默认是小根堆所以取 k 次堆顶元素即可删除堆顶元素后会调整堆中的数据。 代码 public int[] smallestK(int[] arr, int k) {//存储最小K个数的数组int[] ret new int[k];if (arr null || k 0) {return ret;}// 以数组长度初始化一个小根堆QueueInteger minHeap new PriorityQueue(arr.length);//遍历数组 放进小根堆for (int value : arr) {minHeap.offer(value);}//取 k个堆顶元素for (int i 0; i k; i) {ret[i] minHeap.poll();}return ret; }上面这段代码会使时间复杂度升高每添加或删除一个元素就会调整一个接近数组长度的堆。 思路二要求最小 k 个数我们将数组里的前 k 个元素添加到一个大小为 k 的大根堆因为是大根堆所以堆顶元素是堆中最大的元素然后遍历数组剩下的元素如果数组剩下的元素比堆顶元素小我们就删除堆顶元素并添加数组的元素如果数组剩下的元素比堆顶元素大它就不会是前 k 个最小数。 代码 public int[] smallestK(int[] arr, int k) {int[] ret new int[k];if (arr null || k 0) {return ret;}//提供比较器重写compare方法此时建立的就是大根堆QueueInteger maxHeap new PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});//将数组前k个元素添加到大根堆中for (int i 0; i k; i) {maxHeap.offer(arr[i]);}//遍历数组未添加到堆中的元素for (int i k; i arr.length; i) {//因为是求最小值所以如果比大根堆的堆顶元素小就删除堆顶元素并添加这个元素到堆中if (arr[i] maxHeap.peek()) {maxHeap.poll();maxHeap.offer(arr[i]);}}//将堆中的k个元素添加中数组中for (int i 0; i k; i) {ret[i] maxHeap.poll();}return ret; }这段代码中只建立了 k 个容量大小的堆调整的个数就比第一段代码少。 对于求一组数据中前 k 个最大或最小的元素时数据少时我们可以排序但对于数据特别多时还是采用堆的方式比较合适。步骤如下 用数据集合中前K个元素来建堆。 求前 k 个最大的元素则建小堆 求前 k 个最小的元素则建大堆用剩余的 N-K 个元素依次与堆顶元素来比较不满足则替换堆顶元素堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。