2024年java编程基础堆数组

大家好，我是讯享网，很高兴认识大家。

一、堆的创建

1、向下调整（以小堆为例） java编程基础堆数组

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

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

parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记
将parent与较小的孩子child比较，如果：

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

public void shiftDown(int[] elem,int parent,int len){ int cur=parent*2+1; while(cur<len){ if(cur+1<len){ if(elem[cur+1]<elem[cur]){ cur++; } } if(this.elem[cur]<this.elem[parent]) { swap(cur, parent); } parent=cur; cur=parent*2+1; } }

讯享网

2、创建堆

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

3、创建堆的时间复杂度

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

二、堆的插入和删除

1、堆的插入

将要插入的元素放在堆的最后，如果放不了，进行扩容
将新插入的节点向上调整，直到满足堆的性质

【向上调整】

讯享网public void shiftUp(int elem[],int child){ int parent=(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个大或者小的元素，一般数据量都比较大。

class Solution { public int[] smallestK(int[] arr, int k) { int[] array=new int[k]; if(arr==null||arr.length<=k||k==0){ return array; } PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->b-a); int i=0; for(;i<k;++i){ queue.offer(arr[i]); } while(i<arr.length){ if(arr[i]<queue.peek()){ queue.poll(); queue.offer(arr[i]); } i++; } int size=queue.size(); for(int j=0;j<size;++j){ array[j]=queue.poll(); } return array; } }

四、常用接口的介绍

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方法即可 class IntCmp implements Comparator<Integer>{ @Override public int compare(Integer o1, Integer o2) { return o2-o1; } } PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());

2、优先级队列的构造

构造器功能介绍PriorityQueue()创建一个空的优先级队列，默认容量是11PriorityQueue(int
initialCapacity)创建一个初始容量为initialCapacity的优先级队列，注意：
initialCapacity不能小于1，否则会抛IllegalArgumentException异
常PriorityQueue(Collection<?
extends E> c)用一个集合来创建优先级队列