java数据结构中的堆怎么应用-mile米乐体育

java数据结构中的堆怎么应用

本篇内容介绍了“java数据结构中的堆怎么应用”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

一、堆的创建

1、向下调整（以小堆为例）

让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)

如果parent的左孩子存在，即:child < size， 进行以下操作，直到parent的左孩子不存在：

• parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记

• 将parent与较小的孩子child比较，如果：

parent小于较小的孩子child，调整结束否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足堆的性质，因此需要继续向下调整，即parent = child；child = parent*2 1; 然后继续2。

publicvoidshiftdown(int[]elem,intparent,intlen){intcur=parent*2 1;while(cur

2、创建堆

对于普通序列，我们需要从它的第一个有左节点的父节点开始调整，知道整棵树满足堆的性质。

3、创建堆的时间复杂度

堆必须是完全二叉树，满二叉树也是完全二叉树。由下面的计算，创建堆的时间复杂度为o(n).

二、堆的插入和删除

1、堆的插入

• 将要插入的元素放在堆的最后，如果放不了，进行扩容

• 将新插入的节点向上调整，直到满足堆的性质

【向上调整】

publicvoidshiftup(intelem[],intchild){intparent=(child-1)/2;while(parent>=0){if(elem[child]>elem[parent]){swap(child,parent);child=parent;parent=(child-1)/2;}else{break;}}}

2、堆的删除

根据堆的性质，对删除的一定是堆顶元素。步骤如下：

• 将堆顶元素和最后一个元素交换

• 堆的元素个数减一

• 对堆顶元素进行向下调整

三、堆的应用

1、堆排序

升序：创建大根堆

降序：创建小根堆

交换堆顶元素和堆得最后一个元素，进行向下调整，直到堆有序。

2、top-k问题【求最小的k个数】

top-k问题：求数据集合中前k个大或者小的元素，一般数据量都比较大。

classsolution{publicint[]smallestk(int[]arr,intk){int[]array=newint[k];if(arr==null||arr.length<=k||k==0){returnarray;}priorityqueuequeue=newpriorityqueue<>((a,b)->b-a);inti=0;for(;i

四、常用接口的介绍

1、priorityqueue的特性

java集合框架中提供了priorityqueue和priorityblockingqueue两种类型的优先级队列。priorityqueue是线程不安全的，priorityblockingqueue是线程安全的，本文主要介绍priorityqueue。

【priorityqueue】使用的注意事项：

• 必须导入peioriryqueue的包；

• 放置的元素必须是能够比较大小的，否则会抛出classcastexception异常；

• 不能放置null元素，否则会抛出nullpointerexception；

• 可以插入任意多的元素，内部会自动扩容；

• 底层使用了堆数据结构，默认是小堆。如果要构建大堆，则需要提供比较器。

priorityqueue的扩容方式：

• 如果容量小于64时，是按照oldcapacity的2倍方式扩容的

• 如果容量大于等于64，是按照oldcapacity的1.5倍方式扩容的

• 如果容量超过max_array_size，按照max_array_size来进行扩容

int newcapacity = oldcapacity ((oldcapacity < 64) ?

(oldcapacity 2) :

(oldcapacity >> 1));

priorityqueue采用了：comparble和comparator两种方式。

1. comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现comparble接口，并覆写compareto方法

2. 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现comparator接口并覆写compare方法

//用户自己定义的比较器：直接实现comparator接口，然后重写该接口中的compare方法即可classintcmpimplementscomparator{@overridepublicintcompare(integero1,integero2){returno2-o1;}}priorityqueuep=newpriorityqueue<>(newintcmp());

2、优先级队列的构造

“java数据结构中的堆怎么应用”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注恰卡编程网网站，小编将为大家输出更多高质量的实用文章！