优先级队列(堆)
1.二叉树的存储顺序2.1 *** 作—向下调整：2.2建堆的时间复杂度分析**3.** 堆的应用：优先级队列
**3.1** **概念****3.2** **内部原理****3.3** ** *** 作**-入队列**3.4** *** 作-出队列（优先级最高）3.5 **返回队首元素（优先级最高）** **4.** **堆的其他应用**-TopK **问题**5.面试题**6.** 堆的其他应用-堆排序 **java**对象的比较
集合框架中PriorityQueue的比较方式模拟实现PriorityQueue
堆的概念及实现掌握PriorityQueue的使用 1.二叉树的存储顺序
1.1 使用数组保存二叉树结构，通过层序便利的方式去将二叉树的每个节点放入数组中。
而且用于完全二叉树，因为非完全二叉树在数组中存储会有空间的浪费，这种方式就是用堆表示
2.知道双亲或者孩子节点的下标，可以求出另一个的下标，在下面实现堆的代码时有用。
3.小根堆和大根堆：
4.堆的概念：
堆逻辑上是一棵完全二叉树
堆物理上是保存在数组中
5.堆的基本作用是，快速找集合中的最值
2.1 *** 作—向下调整：
前提：左右子树必须已经是一个堆，才能调整
向下调整的代码：
public class Heap {
public int[] elem;
public int usedSize;
public Heap(){
this.elem = new int[10];
}
public void swap(int child,int parent){
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
}
public void shiftDown(int parent,int len){
int child = parent*2+1;
while (childelem[parent]) {
swap(child, parent);
//当孩子和双亲交换后，我们开始向下检测去重新赋值
parent = child;
child = parent*2+1;
}else{
//不需要交换的时候，表明此树满足，那么没有交换，下面本来就已经调整完了，之所以向下检测是因为你上面的书发生了交换可能导致下面的树不满足了。
//所以直接break结束本次循环，继续另一棵树
break;
}
}
}
//创建一个堆，等会进行向下调整
public void creatHeap(int[] array){
//这里是把传入的数组进行接收
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
//根据代码显示 时间复杂度为nlogn 实际上是n，具体可以看板书
for (int parent = (usedSize-1-1)/2; parent >=0 ; parent--) {
shiftDown(parent,usedSize);//这里传的usedSize 而不是array.length 需要的是传过来的元素，可能array后面很多都是0
}
}
}
2.2建堆的时间复杂度分析
最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度
3. 堆的应用：优先级队列 3.1 概念
在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次
高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。
在这种情况下，我们的数据结构应该提供两个最基本的 *** 作，一个是返回最高优先级对象，一个是添加新的对象。这
种数据结构就是优先级队列(Priority Queue)
3.2 内部原理优先级队列的实现方式有很多，但最常见的是使用堆来构建。
3.3 *** 作-入队列过程（以大堆为例）：
首先按尾插方式放入数组
比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
否则，交换其和双亲位置的值，重新进行 2、3 步骤
直到根结点
//向上调整：入队列
private void shiftup(int child){
int parent = (child-1)/2;
while(child>0){
if(elem[child]>elem[parent]){
swap(child,parent);
}
child = parent;
parent = (child-1)/2;
}
}
public void offer(int val){
if(isFull()){
this.elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
shiftup(usedSize-1);
}
public boolean isFull(){
return usedSize == elem.length;
}
3.4 *** 作-出队列（优先级最高） 3.5 返回队首元素（优先级最高）
删除堆顶元素
返回堆顶元素即可
为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向
下调整方式重新调整成堆
//出队列：最后一个元素与0下标进行交换，然后usedSize--即可
public int poll(){
if(isEmpty()){
throw new RuntimeException("优先级队列为空！");
}
int tmp = elem[0];
elem[0] = elem[usedSize-1];
elem[usedSize-1] = tmp;
usedSize--;
shiftDown(0,usedSize);
return tmp;
}
public boolean isEmpty(){
return usedSize == 0;
}
public int peek(){
if(isEmpty()){
throw new RuntimeException("优先级队列为空！");
}
return elem[0];
}
4. 堆的其他应用-TopK 问题
总结：如果求前k个最大的元素，就要建小根堆
如果求前k个最小的元素，就要建大根堆
如果求第k个最大的元素，就要建小根堆，堆顶元素就是第k大的元素
如果求第k个最小的元素，就要建大根堆，堆顶元素就是第k小的元素
TopK的代码，有一题还是关于找出和最小的k对数字
public class TopK {
public static int[] topK(int[] array,int k){
//创建一个大根堆
PriorityQueue maxHeap = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for (int i = 0; i < array.length; i++) {
if(maxHeap.size() < k ){
maxHeap.offer(array[i]);
}else{
int tmp = maxHeap.peek();
if(tmp > array[i]){
maxHeap.poll();
maxHeap.offer(array[i]);
}
}
}
int[] tmp = new int[k];
for (int i = 0; i < tmp.length; i++) {
tmp[i] = maxHeap.poll();
}
return tmp;
}
public static void main(String[] args) {
int[] array = {18,21,8,10,34,12};
int[] tmp = topK(array,3);
System.out.println(Arrays.toString(tmp));
}
}
5.面试题
//力扣373.查找和最小的k对数字：也是利用TopK解决
public static List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue> maxHeap = new PriorityQueue<>(k, new Comparator>() {
@Override
public int compare(List o1, List o2) {
return (o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1));
}
});
for (int i = 0; i < Math.min(nums1.length,k); i++) {
for (int j = 0; j < Math.min(nums2.length,k); j++) {
if(maxHeap.size() < k){
List tmpList = new ArrayList<>();
tmpList.add(nums1[i]);
tmpList.add(nums2[j]);
maxHeap.offer(tmpList);
}else{
int top = maxHeap.peek().get(0)+maxHeap.peek().get(1);
if(top > nums1[i]+nums2[j]){
//d出
maxHeap.poll();
List tmpList = new ArrayList<>();
tmpList.add(nums1[i]);
tmpList.add(nums2[j]);
maxHeap.offer(tmpList);
}
}
}
}
List> ret = new ArrayList<>();
for (int i = 0; i < k && !maxHeap.isEmpty(); i++) { //这里还需要加个条件：！maxHeap不为空，有一种情况是：
//你本身就是给的两个数组，只能组成的对数比k还小，那么你就只能把有的都出了，痛出不了k对数，所以最后堆为空了就不能出了
ret.add(maxHeap.poll());
}
return ret;
}
6. 堆的其他应用-堆排序
对一组数据进行从小到大排序：
1.调整完大根堆
2.将0下标和最后一个元素进行交换，然后进行调整：每次将数组最大的元素放在后面，便可以从小到大排序
3.不断循环，end–（end = 0结束）****
public void heapSort(){
int end = usedSize-1;
while(end>0){
swap(0,end);
shiftDown(0,end);//这里传的是useSize-1 而不是usedSize ，在原本的函数里传的是不减1，但此时你每循环一次，你的最后一个元素都确定了，
//此时你调整的这棵树就是0（因为你当时把堆顶换了）作为双亲，然后你结束的位置是变的，第二次就是去确定倒数第二个元素，每次都要减1
end--;
}
}
java对象的比较
问题的提出元素的比较Java中对象的比较集合框架中PriorityQueue的比较方式模拟实现PriorityQueue
上节课我们讲了优先级队列，优先级队列在插入元素时有个要求：插入的元素不能是null或者元素之间必须要能够
进行比较，为了简单起见，我们只是插入了Integer类型，那优先级队列中能否插入自定义类型对象呢？
<" />
集合框架中PriorityQueue的比较方式
模拟实现PriorityQueue
比较器来实现比较 class RankComparator implements Comparator{ @Override public int compare(Card o1, Card o2) { return o1.rank-o2.rank; } } public class TestDemo { public static void main(String[] args) { PriorityQueue cards = new PriorityQueue<>(); Card card1 = new Card(1,"♥"); Card card2 = new Card(2,"♥"); RankComparator rankComparator = new RankComparator(); PriorityQueue priorityQueue = new PriorityQueue<>(rankComparator);//这里你需要传比较器，指定比较器的比较方式没否则你是默认比较， //但是你又没有指定属性去比较，就会报错 //这种写法也是可以，内部类的写法 priorityQueue.offer(card1);//直接放到底层的queue数组的0下标 priorityQueue.offer(card2); System.out.println(priorityQueue); }
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）