汕头建站服务,安徽省水利厅网站 基本建设,福州闽侯网站建设,网页制作素材和实例找往期文章包括但不限于本期文章中不懂的知识点#xff1a; 个人主页#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏#xff1a;数据结构#xff08;Java版#xff09; 目录
堆的概念
堆的创建
时间复杂度分析#xff1a;
堆的插入与删除
优先级队列
PriorityQ…找往期文章包括但不限于本期文章中不懂的知识点 个人主页我要学编程(ಥ_ಥ)-CSDN博客 所属专栏数据结构Java版 目录
堆的概念
堆的创建
时间复杂度分析
堆的插入与删除
优先级队列
PriorityQueue的特性
PriorityQueue源码分析
PriorityQueue常用接口介绍
构造方法
堆的应用 堆的概念
如果有一个关键码的集合K {k0k1 k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储从上到下、从左到右在 一个一维数组 中并满足Ki K(2i1) 且 KiK(2i2) (Ki K(2i1) 且 Ki K(2i2) ) i 012…则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。
注意Ki K(2i1) 且 KiK(2i2) 这个公式就是说明根结点的值小于等于左右孩子节点的值即小根堆或者最小堆。与其相反就是根结点的值大于等于左右孩子节点即大根堆或者最大堆。
堆的性质
1、堆中某个节点的值总是不大于或不小于其父节点的值
例如小根堆就是根结点的值小于等于孩子节点的值也就是说孩子节点的值大于等于根结点的值也就对应了孩子节点不小于其父节点反之就是大根堆的性质了。
2、堆总是一棵完全二叉树。
因为堆是把数据按照完全二叉树的方式存储在一个一维数组中的。
3、堆的根结点总是这个一维数组中的最值要么是最大值要么是最小值。
如果是大根堆按照 性质1 的推论就是根结点的值大于等于孩子节点的值。这样一直递归下去根结点肯定就是最大的。最坏情况就是所有结点的值全部相等。
4、堆的存储结构是一个一维数组但是其逻辑结构是一个完全二叉树。
为什么不能是一个普通的二叉树呢因为普通的二叉树会有空节点空树这样在数组中就会null元素的存在导致了空间利用率比较低。
堆的创建
现有一组数据 {0,1,2,3,4,5,6,7,8,9} 我们要把这组数据组织成大根堆。
public class Heap {int[] elem;int usedSize;public Heap(int k) {elem new int[k];}public Heap() {elem new int[10];}// 给堆初始化数据public void initHeap(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--) {// 向下调整的方法从要调整的位置开始到整棵树结束siftDown(parent, usedSize);}
}private void siftDown(int parent, int usedSize) {int child parent * 2 1;// 只有当孩子节点在有效数据之内时才能调整while (child usedSize) {// 先找到左右孩子节点的最大值if (child1 usedSize elem[child] elem[child1]) { // 得确保右孩子存在child;}// 比较孩子节点的最大值和根结点的值if (elem[parent] elem[child]) {// 交换swap(elem, parent, child);// 交换完成只是本级满足了大根堆的条件但是交换下去的值不一定满足当级的大根堆条件parent child;child parent * 2 1;} else {// 满足大根堆就不需要继续调整了break;}}
}private void swap(int[] elem, int i, int j) {int tmp elem[i];elem[i] elem[j];elem[j] tmp;
} 这里可能有几个小伙伴们疑惑的地方
1、为什么交换完成之后还要再进行向下调整判断是否需要交换 总而言之就是一句话参与调整的就得再次进行判断是否符合大根堆。
2、为什么本级满足大根堆的情况后就不需要继续往下判断是否调整
因为我们是从下面开始调整的如果本级满足了大根堆那么下面的就一定也满足大根堆。因此就无需继续判断了。
时间复杂度分析 将上面的所有结果相加就是最终的时间复杂度。 因此向下调整建堆的时间复杂度是O(N)。
堆的插入与删除
堆的插入
思路因为堆在存储上是一个数组那么我们肯定是按照插入数组元素的方法来进行插入即尾插。尾插完之后还得进行判断这个新的堆是否是大根堆。因为这个的判断方式是从插入的节点开始往上判断因此这个判断是向上调整。 public void offer(int val) {// 插入的元素放到最后然后其所在的树进行向上调整// 判满扩容if (isFull()) {elem Arrays.copyOf(elem, elem.length*2);}elem[usedSize] val;siftUp(usedSize-1, 0);}private boolean isFull() {return usedSize elem.length;}private void siftUp(int child, int end) {// 因为原来是满足大根堆的因此我们只需要判断这个新插入的元素是否也满足int parent (child-1) / 2;while (parent end) {if (elem[child] elem[parent]) {// 交换swap(elem, child, parent);child parent;parent (child-1) / 2;} else {// 因为原来是满足大根堆的如果这个也满足那么就全部满足了break;}}}
有了插入方法我们也就可以通过插入来创建堆了。
注意我们手动创建堆的方法是采用向下调整而插入元素采用的是向上调整。因此两者创建出来的堆结果会不一样但都是大根堆。
向上调整建堆的时间复杂度分析
与向下调整相比向上调整还要把最后一层的节点全部调整因此向上调整的时间复杂度肯定是大于向下调整的。 向上调整建堆的时间复杂度O(NlogN) 。 堆的删除
思路堆的删除我们采取的方式也和数组类似是把堆顶元素与最后一个元素交换再进行向下调整。 public int poll() {// 判空抛异常if (isEmpty()) {throw new HeapIsEmptyException(堆为空异常);}int val elem[0];swap(elem, 0, usedSize-1);siftDown(0, usedSize-1);usedSize--;return val;}private boolean isEmpty() {return usedSize 0;}
堆的删除的时间复杂度O(logN)。
交换完向下调整就只调整树的高度也就是logN。
堆的插入的时间复杂度O(logN)。
插在最后然后进行向上调整也是调整树的高度。
获取堆顶元素 public int peek() {if (isEmpty()) {throw new HeapIsEmptyException(堆为空异常);}return elem[0];}
看到这里我们就应该可以猜出堆和队列是有关系的否则不会把队列的方法名给堆。堆这种数据结构可以实现优先级队列。
优先级队列
通过堆的性质3我们就可以推出一个结论如果我们每次从堆中删除数据一定删除的是优先级最高的。如果是小根堆那么就是删除最小值如果是大根堆那么删除的就是最大值。即优先级最高的先被删除。这就对应了队列中的一个特殊队列优先级队列。实际上JavaAPI中优先级队列底层就是通过堆来实现的。
PriorityQueue的特性
1、使用时必须导入PriorityQueue所在的包即
import java.util.PriorityQueue;
2、PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出 ClassCastException异常。
因为堆中的元素是需要可以比较大小。否则无法判别优先级。
3、不能插入null对象否则会抛出NullPointerException。
因为我们去比较的时候是通过对象调用专属的比较方法如果对象为null就会发生空指针异常。
4、PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素。
5、其内部可以自动扩容无需我们主动实现。
PriorityQueue源码分析 PriorityQueue常用接口介绍
构造方法
构造器功能介绍PriorityQueue()创建一个空的优先级队列默认容量是11PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列注意 initialCapacity不能小于1否则会抛IllegalArgumentException异常PriorityQueue(Collection c)用一个集合来创建优先级队列
使用
public class Test {public static void main(String[] args) {// 创建一个优先级队列默认容量11PriorityQueueInteger priorityQueue1 new PriorityQueue();// 创建一个优先级队列容量是20PriorityQueueInteger priorityQueue2 new PriorityQueue(20);ListInteger list new ArrayList();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);// 创建一个优先级队列容量根据list的大小来分配PriorityQueueInteger priorityQueue3 new PriorityQueue(list);// 长度System.out.println(priorityQueue3.size());// 小根堆System.out.println(priorityQueue3.poll());}
}
这里的“容量根据list的大小来分配”的意思是本来的默认容量是11如果list的长度大于11那么就会按照2倍或者1.5倍去扩容。
插入/删除/获取优先级最高的元素
函数名功能介绍boolean offer(E e)插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常时间复杂度O(log2 N)注意空间不够时候会进行扩容E peek()获取优先级最高的元素如果优先级队列为空返回nullE poll ()移除优先级最高的元素并返回如果优先级队列为空返回nullint size()获取有效元素的个数void clear()清空boolean isEmpty()检测优先级队列是否为空空返回true
堆的应用
1、PriorityQueue的实现。
2、堆排序。
不同的顺序建立不同的堆但是一定是后面的元素先有序再是前面的元素有序。
因此我们就可以知道如果是从小到大排序那么就要建大根堆反之则是建小根堆。
因为 如果是从小到大排序且后面的元素先有序那么后面的元素只能是最大的因此建立大根堆的话堆顶元素一定是最大的。这时我们只需把堆顶元素和最后一个元素进行交换然后再进行向下调整直至调整到整棵树的根节点。
代码实现 public void heapSort() {int j 0;for (int i usedSize-1; i 0; i--) {swap(elem,i,j);siftDown(0, i);}}
3、Top-k问题
TOP-K问题即求数据集合中前K个最大的元素或者最小的元素一般情况下数据量都比较大且K都比较小。
例如全球前500强的企业。
对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
如果是要找前K个最小的元素将前K个元素建成大根堆然后再去遍历后N-K个元素遇到小于堆顶元素的就交换遍历完成后剩下的堆中元素就是前K个最小的。
练习面试题 17.14.最小K的个数
题目 设计一个算法找出数组中最小的k个数。以任意顺序返回这k个数均可。 示例 输入 arr [1,3,5,7,2,4,6,8], k 4
输出 [1,2,3,4]提示 0 len(arr) 1000000 k min(100000, len(arr)) 思路一直接排序然后遍历前K个即可。 public int[] smallestK(int[] arr, int k) {// 调用JavaAPI提供的方法才行自己实现的方法会超出时间限制Arrays.sort(arr); // 默认是从小到大排序int[] ret new int[k];for (int i 0; i k; i) {ret[i] arr[i];}return ret;}思路二将N个元素建成小根堆然后每次取堆顶元素取K次即可。 public int[] smallestK(int[] arr, int k) {PriorityQueueInteger priorityQueue new PriorityQueue();for (int i 0; i arr.length; i) {priorityQueue.offer(arr[i]);}// 上面是建成的小根堆int[] ret new int[k];for (int i 0; i k; i) {ret[i] priorityQueue.poll();}return ret;}
思路三取前K个元素建成大根堆然后再遍历剩下的元素如果小于堆顶元素则交换。
class Solution {public int[] smallestK(int[] arr, int k) {int[] ret new int[k];if (k 0 || arr null) {return ret;}PriorityQueueInteger priorityQueue new PriorityQueue(k, new Incompare());for (int i 0; i k; i) {priorityQueue.offer(arr[i]);}for (int i k; i arr.length; i) {if (priorityQueue.peek() arr[i]) {priorityQueue.poll();priorityQueue.offer(arr[i]);}}for (int i 0; i k; i) {ret[i] priorityQueue.poll();}return ret;}
}// 创建新的比较器
class Incompare implements ComparatorInteger {Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}好啦本期 数据结构之探索“堆”的奥秘 的学习之旅就到此结束啦我们下一期再一起学习吧
