当前位置:   article > 正文

【数据结构】堆_堆数据结构

堆数据结构

目录

1、优先级队列

1.1、概念

2、优先级队列的模拟实现

2.1、堆的概念

2.1.1、堆的性质

2.1.2、画图理解大根堆和小根堆 

 2.2、堆的存储方式

 2.3、堆的创建

2.3.1、堆向下调整

2.3.3、建堆的时间复杂度(向下调整)

2.4、堆的插入与删除

2.4.1、堆的插入

2.4.2、向上调整的时间复杂度 

2.4.3、堆的删除

3、优先级队列常用接口

3.1、priorityQueue的特性

3.2、PriorityQueue常用接口的介绍

1、PriorityQueue的构造方法

2、在JDK1.8中,PriorityQueue的扩容方式:

3.3、 练习题

 4、对象的比较

 4.1、比较方法

4.1.1、利用==比较(比较地址)

4.1.2、使用equals()方法进行比较(比较是否相同)

 4.1.3、实现对象大小的比较

4.1.4、三种比较方法的对比

4.2、 集合框架中PriorityQueue的比较方式


1、优先级队列

1.1、概念

队列我们在前面已经了解过了,队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级一般出队列时,可能需要优先级高的元素先出队列,该种场景下,使用队列显然不合适,比如:在手机上玩手机的时候,如果有来电,那么系统应该优先处理打进来的电话;

在这种情况下,数据结构应该提供两个最基本的操作一个返回最高优先级对象一个是添加新的对象这种数据结构就是优先级队列(PriorityQueue)。

2、优先级队列的模拟实现

JDK1.8种的PriorityQueue底层使用了堆这种数据结构,而堆实际就是完全二叉树的基础上进行了一些调整。

2.1、堆的概念

如果有一个关键码的集合K={K0,K1,K2,....,Kn-1},把它的所有元素按完全二叉树的顺序存储方式存储在一维数组中,并满足:K_{i}<=K_{_2i+1}且  K_{i}<=K_{2i+2}K_{i}>=K_{2i+1}K_{i}>=K_{2i+2})i=0,1,2....,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或者大根堆根节点最小的堆称为最小堆或者小根堆。 

2.1.1、堆的性质

  • 堆中某个结点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

2.1.2、画图理解大根堆和小根堆 

 2.2、堆的存储方式

从堆的概念可知,堆是一棵完全二叉树因此可以采用层序遍历的方式来高效存储

❓❓❓为什么堆一定要是完全二叉树

  • 因为在将完全二叉树的结点放入数组中的时候,每个数组元素中都有内容。
  • 第二点为下边的注意事项

❗❗❗ 注意:对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空结点,就会导致空间的利用率比较低。

将元素存储到数组中后,可以根据二叉树的性质对树进行还原。假设i为结点在数组中的下标,则有: 

  • 如果i为0,则i表示的结点为根节点,否则i结点的双亲结点为(i - 1)/2
  • 如果2*i + 1小于节点个数,则结点i的左孩子下标为2*i+1,否则没有左孩子
  • 如果2*i+2小于结点个数,则结点i的有孩子下标为2*i+2,否则没有有孩子

 2.3、堆的创建

2.3.1、堆向下调整

  • 这里的向下调整,表示每棵子树都是从父结点开始向下走,但是在将每颗子树创建成堆的时候还是从子树向上(父节点)比较。
  • 在创建堆时,从孩子结点向上比较,交换结点,但是当一个结点,进行交换完成之后,它的孩子结点形成的子树不满足大根堆或者小根堆时,就需要再次比较孩子节点与父节点值得大小比较,交换得操作。这就叫向下调整。

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据,如果将其创建成堆呢?

以大根堆为例

代码示例:

  1. public class TestHeap {
  2. public int[] elem;
  3. public int usedSize;
  4. public TestHeap(){
  5. this.elem = new int[10];
  6. }
  7. //初始化数组
  8. public void initElem(int[] array){
  9. for (int i = 0; i < array.length; i++) {
  10. elem[i] = array[i];
  11. usedSize++;
  12. }
  13. }
  14. //创建堆
  15. public void createHeap(){
  16. //确定每颗子树的父亲节点,一棵子树创建成堆之后,再重新向下调整另一颗子树
  17. for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {//这里从最后一位数组元素开始,找其结点,找父节点的公式为(i-1)/2,usedSize记录数组中的元素,所以数组最后一个元素为usedSize-1
  18. shiftDown(parent,usedSize);//将usedSize作为结束条件,每个父亲结点的孩子结点的下标都不可能超过数组的长度。如果再向下调整,一定会超过数组长度,结束调整。
  19. }
  20. }
  21. //向下调整,传父亲结点的下标,和每课树的结束下标
  22. private void shiftDown(int parent,int len){
  23. int child = 2*parent+1;
  24. //最起码 要有左孩子,左孩子结点下标小于数组长度
  25. while(child < len){
  26. //一定是有有孩子的情况,这样才能找到左右孩子结点的最大值。
  27. if(child+1<len && elem[child] < elem[child+1]){//如果有孩子结点大于左孩子结点,那么孩子结点的下标++,保证child下标一定是左右孩子最大值的下标
  28. child++;
  29. }
  30. //比较最大孩子结点与父亲结点的值,最大值放到父亲结点的位置。
  31. if(elem[child] > elem[parent]){
  32. int tmp =elem[child];
  33. elem[child] = elem[parent];
  34. elem[parent] = tmp;
  35. parent = child;//交换完成之后,父节点指向其左孩子结点
  36. child = 2*parent+1;//child指向子树的孩子结点,通过循环,将子树建成堆
  37. }else{//如果最大孩子结点的值比父亲结点的值小,则直接结束。
  38. break;
  39. }
  40. }
  41. }
  42. }

注意:在调整以parent为根的二叉树时,必须满足parent的左右子树已经是堆了,才可以向下调整

2.3.3、建堆的时间复杂度(向下调整

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明时间复杂度

  • 向下调整建堆的时间复杂度为:O(N)
  • 堆的向下调整算法的时间复杂度,最坏的情况下,从根一路比较到叶子结点,比较的次数为完全二叉树的高度,时间复杂度为O(logN) .

2.4、堆的插入与删除

2.4.1、堆的插入

堆的插入需要两个步骤:

  1. 先将元素放入到底层空间中(注意:空间不够时需要扩容)
  2. 将最后新插入的结点向上调整,这道满足堆的性质

  

❗❗❗注意: 小根堆在插入新的元素之后,向上调整时,只需要将插入的数字与父节点进行比较就行,因为父节点本身就是最小的。

 代码示例:插入元素采用向上调整的方法

  1. import java.util.Arrays;
  2. public class TestHeap {
  3. public int[] elem;
  4. public int usedSize;
  5. public TestHeap(){
  6. this.elem = new int[10];
  7. }
  8. //初始化数组
  9. public void initElem(int[] array){
  10. for (int i = 0; i < array.length; i++) {
  11. elem[i] = array[i];
  12. usedSize++;
  13. }
  14. }
  15. //向上调整
  16. private void shiftUp(int child){
  17. int parent = (child-1)/2;//利用孩子结点下标求父亲节点下标
  18. while(child>0){//当孩子结点的下标大于0时,进入循环,进行比较,交换
  19. if(elem[child]>elem[parent]){//如果孩子结点的值比父亲结点的值大
  20. int tmp = elem[child];
  21. elem[child] = elem[parent];
  22. elem[parent] = tmp;
  23. child = parent;//交换完成之后,child指向父节点
  24. parent = (child-1)/2;//重新在计算父亲结点的下标,继续比较交换
  25. }else{//如果孩子结点没有父亲结点的值大,直接退出
  26. break;
  27. }
  28. }
  29. }
  30. //插入一个元素
  31. public void offer(int val){
  32. if(isFull()){//如果数组满了之后,则需要扩容
  33. Arrays.copyOf(elem,2*elem.length);//对数组按照其长度的两倍进行扩容
  34. }
  35. elem[usedSize++] = val;//这里表示在数组的usedSize位置存放一个数据,存完之后数组长度+1
  36. }
  37. //判断数组是否已满
  38. public boolean isFull(){
  39. return usedSize == elem.length;//当数组长度等于usedSize时,数组满了。因为在初始化数组时,给定了数组的长度
  40. }
  41. }

2.4.2、向上调整建堆的时间复杂度 

2.4.3、堆的删除

堆的删除一定删除堆顶元素。操作如下

  1. 将堆顶元素对堆中最后一个元素交换
  2. 将堆中有效数据个数减少一个
  3. 对堆顶元素进行向下调整

 代码示例:

  1. import java.util.Arrays;
  2. public class TestHeap {
  3. public int[] elem;
  4. public int usedSize;
  5. public TestHeap(){
  6. this.elem = new int[10];
  7. }
  8. //初始化数组
  9. public void initElem(int[] array){
  10. for (int i = 0; i < array.length; i++) {
  11. elem[i] = array[i];
  12. usedSize++;
  13. }
  14. }
  15. //判断数组是否已满
  16. public boolean isFull(){
  17. return usedSize == elem.length;//当数组长度等于usedSize时,数组满了。因为在初始化数组时,给定了数组的长度
  18. }
  19. //删除堆顶元素
  20. public void pop(){
  21. if(isEmpty()){//如果数组为空,则直接退出
  22. return ;
  23. }
  24. swap(elem,0,usedSize-1);//若不为空,则调用交换方法,交换第一个元素和最后一个元素的位置
  25. usedSize--;//这里就相当于删除
  26. shiftDown(0,usedSize);//调用向下调整的方法,从0下标开始,调整usedSize个元素
  27. }
  28. //判断数组是否为空
  29. public boolean isEmpty(){
  30. return usedSize == 0;
  31. }
  32. //交换方法,给定一个数组,交换其i下标位置的数据和j下标位置的数据
  33. private void swap(int[] array,int i,int j){
  34. int tmp = array[i];
  35. array[i] = array[j];
  36. array[j] = tmp;
  37. }
  38. //向下调整,传父亲结点的下标,和没课树的结束下标
  39. private void shiftDown(int parent,int len){
  40. int child = 2*parent+1;
  41. //最起码 要有左孩子,左孩子结点下标小于数组长度
  42. while(child < len){
  43. //一定是有有孩子的情况,这样才能找到左右孩子结点的最大值。
  44. if(child+1<len && elem[child] < elem[child+1]){//如果有孩子结点大于左孩子结点,那么孩子结点的下标++,保证child下标一定是左右孩子最大值的下标
  45. child++;
  46. }
  47. //比较最大孩子结点与父亲结点的值,最大值放到父亲结点的位置。
  48. if(elem[child] > elem[parent]){
  49. int tmp =elem[child];
  50. elem[child] = elem[parent];
  51. elem[parent] = tmp;
  52. parent = child;//交换完成之后,父节点指向其左孩子结点
  53. child = 2*parent+1;//child指向子树的孩子结点,通过循环,将子树建成堆
  54. }else{//如果最大孩子结点的值比父亲结点的值小,则直接结束。
  55. break;
  56. }
  57. }
  58. }
  59. }

3、优先级队列常用接口

3.1、priorityQueue的特性

Java集合框架中提供了PriorityQueuePriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的,这里主要介绍Priority Queue。

PriorityQueue的使用注意事项:

1、使用时必须导入PriorityQueue所在的包。

import java.util.PriorityQueue

2、PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出ClassCastException异常。

  • 举例:假设现在我们不知道PriorityQueue是一个大根堆还是小根堆,那么给PriorityQueue中传入两个以上的数字,将它的堆顶元素弹出,弹出的是最小的数字,那么PriorityQueue就是小根堆,弹出的是最大的数字,则就是大根堆。Integer 类是实现了Comparable接口的,所以可以比较。

  •  创建两个学生对象,放入PriorityQueue中,编译会报错,因为这两个学生对象,你并没有规定以什么方式去比较。无法比较大小,所以会报错

  • 这里我们来看一下,PriorityQueue中的shifUp(向上调整)方法,源码当中,实现了Comparable和Comparator接口

 ❗❗❗注意:当你自定义一个类的时候,传入PriorityQueue中的对象无法比较时,一定要自己写一个Comparable或者Comparator接口。

3、不能插入null对象,否则会抛出NullPointerException

 来看为什么会抛NullPointerException异常,我们来看以下PriorityQueue 当中的offer方法的源码

 4、最多可以存放堆个大小的数据,一般情况下规定大小为整形的最大值

5、插入和删除的时间复杂度为O(log{_{2}}^{n})

6、PriorityQueue底层使用了堆数据结构

7、PriorityQueue默认情况下是小堆————每次获取到的元素都是最小元素

3.2、PriorityQueue常用接口的介绍

1、PriorityQueue的构造方法

常见的几种构造方法

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

1、PriorityQueue()构造方法

 来看一下带两个参数的构造方法

 2、PriorityQueue(int initialCapacity)构造方法

3、 PriorityQueue(Collection<?extends E> c)构造方法

2、在JDK1.8中,PriorityQueue的扩容方式:

  • 如果容量小于64时,是按照oldCapacity的2倍方式扩容的
  • 如果容量大于等于64,是按照oldCapacity的1.5倍方式扩容的
  • 如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容

3.3、 练习题

设计一个算法,找出数组中最小(大)的k个数。以任意顺序返回这个k个数即可

方法思路:

这里有两种做法:

  1. 将传进来的数组放入到PriorityQueue当中,一小根堆的形式存储。然后再将堆顶元素弹出,弹出一个元素,向下调整一次。直到将数组中前k个最大的元素弹出,方法结束。但是这种方法有一个弊端,就是时间复杂度太大。不是最优解。
  2. 将数组中前k个元素先按照小根堆的方式存储,然后拿数组中剩余的元素,依次和小根堆的堆顶元素(堆中的最小值)进行比较,比堆顶元素大,将堆顶元素弹出,将数组中的元素放入小根堆;比堆顶元素小的,不进入小根堆中。最终将数组中剩余比较完,堆中的元素,就是数组中前k个最小的元素。

这里实现第二种写法

  1. import java.util.PriorityQueue;
  2. import java.util.Queue;
  3. public class TestHeap {
  4. //找出数组中最大的k个数
  5. public int[] maxK(int[] arr, int k) {
  6. int[] ret = new int[k];//用来存放最终形成的前K个最大的值
  7. if (arr == null || k == 0) {
  8. return ret;
  9. }
  10. //创建堆,在堆内部的数组中,开辟k个空间
  11. Queue<Integer> minheap = new PriorityQueue<>(k);
  12. //遍历数组的前k个放入到堆中
  13. for (int i = 0; i < k; i++) {
  14. minheap.offer(arr[i]);//将传进来的数组元素放入到堆中
  15. }
  16. //假设数组长度为c
  17. //遍历剩下的c-k个,每次和堆顶元素进行比较
  18. for (int i = k; i < arr.length; i++) {
  19. if (arr[i] > minheap.peek()) {//比较堆顶元素和数组中剩余元素的大小
  20. minheap.poll();//弹出堆顶元素
  21. minheap.offer(arr[i]);//将数组中的元素放入堆中
  22. }
  23. }
  24. for (int i = 0; i < k; i++) {
  25. ret[i] = minheap.poll();//弹出堆顶元素,用ret数组接收
  26. }
  27. return ret;//最后将ret返回给调用者
  28. }
  29. }
  • 因为第一个for循环中,offer插入元素之后,还要发生向上调整,向上调整的时间复杂度为NlogN,所以第一次for的时间复杂度为:k*logk,
  • 第二个for循环中,与第一次相似,将堆顶元素弹出之后,插入新的元素,还要发生向上调整,所以第二个for的时间复杂度为:(N-K)logk
  • 两次for循环的时间复杂度相加结果为:O(Nlogk)

❗❗❗注意:

  • 要找数组中前k个最大的数,则需要创建小根堆,用小根堆中最小的数(堆顶元素),和数组中的数进行比较,堆顶元素小,将堆顶元素弹出,放入数组中的元素,这样循环,就会将数组中前k个最大的数找到。
  • 找数组中前k个最小的数,则需要创建大根堆,用大根堆中最大的数(堆顶元素),和数组中的数进行比较,堆顶元素大,将堆顶元素弹出,将数组中的元素放入堆中,这样循环,就会找到前k个最小的数。

 4、对象的比较

优先级队列在插入元素的时候有一个要求:插入的元素不能是null或者元素之间必须要能够进行比较,我们插入Integer类型,可以进行比较,是因为Integer实现了Comparable接口,但是我们自定义的类没有实现Comparable接口,创建的对象无法进行直接比较。

优先级队列的底层使用的是堆,而向堆中插入元素时,为了满足堆的性质,必须要进行元素的比较。因此会抛出异常。

 4.1、比较方法

4.1.1、利用==比较(比较地址)

 这样比较只是,表示两个对象的地址不同,并不能比较大小。

4.1.2、使用equals()方法进行比较(比较是否相同)

 结果与用==比较的结果相同,我们来看以下equals方法的源码,student类并没有写equals方法,但是我们使用student1调用了equals方法,说明equals方式属于Object类当中。

equals方法在Object类当中的实现方法,与用==比较同理。所以这里使用equals方法比较的是两个对象的地址。 

但是我们可以在Student类当中自己实现equals方法,用来比较两个对象

 再次使用equals方法进行比较,输出结果为true,但是只能说明两个对象是否相等,并不能比较对象的大小。

 4.1.3、实现对象大小的比较

1、在自定义类当中实现Comparable接口,重写Comparable接口中的compareTo方法。

指定以自定义对象的那个属性进行计较,那么在之后使用student对象进行比较的时候,就会使用那个属性进行比较。

 谁调用compareTo方法,谁就是this,上述中

student1的age比student2的age大,返回正数。

student1的age比student2的age小,返回负数。

student1的age与student2的age相等,返回0。

❗❗❗这样写的弊端就是将比较方法写死了,是对象的比较不够灵活。

要解决这种问题,我们就要说到比较器了。

2、实现比较器

创建一个类实现Comparator接口,再重写compare 方法,用Comparator接口规定的类的属性进行比较。

这里使用对象的name进行比较,对象的name是引用类型,不能使用减法去比较大小,所以这里调用String自己实现的compareTo方法进行比较。调用String类的方法是因为,name是String类型的。 

 调用compare方法,进行比较两个对象。

 如果student1.name > student2.name,返回一个正数

 如果student1.name < student2.name,返回一个负数

 如果student1.name = student2.name,返回0

上面写了一个以名字的方式比较对象大小的比较器。当然我们也可以写一个以年龄比较对象大小的比较器。

 如果student1.age > student2.age,返回一个正数

如果student1.age < student2.age,返回一个负数

如果student1.age = student2.age,返回0

4.1.4、三种比较方法的对比

方法说明
Object.equals因为所有类都是继承自Object的,所以直接重写即可,不过只能比较相等与否
Comparable.compareTo需要手动实现接口,局限性强,写好之后,每次用该类,需要比较对象大小时,只能使用写好的比较方法,别人不能修改。
Comparator.compare需要实现一个比较器对象,再比较对象的时候,可以灵活使用不同的比较器。

4.2、 集合框架中PriorityQueue的比较方式

 集合框架中的PriorityQueue底层使用堆结构,因此其内部的元素必须要能够比较大小,PriorityQueue采用了Comparable和Comparator两种方式。

  1. Comparable是默认的内部比较方式,如果用户插入(offer)自定义类型的对象时,该类对象必须要实现Comparable接口,并重写compareTo方法
  2. 用户也可以选择使用比较器对象,如果用户插入自定义类型对象时,必须提供一个比较器类,让该类实现Comparator接口并重写compare方法。

举例说明:

1、使用Comparable接口,插入的数据类型实现Comparable接口,重写compareTo方法就可以,进行比较。

创建一个PriorityQueue对象,调用offer方法。

 进入PriorityQueue类中,查看offer方法源码。

用e来接收传进来的数字,如果传给e的是一个基本类型的变量,会发生装包。然后判断e是否为空,为空抛异常,不为空,size记录数组中元素的个数,i也是用来记录数组中元素的个数,如果数组当中的元素个数比数组长或者相等,则给数组扩容,如果小于则不进,size+1,表示插入一个数。当数组为空时,插入的数,直接放入0下标位置,否则,就需要调用siftUp()方法。

当再插入一个数时,i不等于0,就会调用向上调整的方法,判断comparator是否为空,因为之前在创建PriorityQueue对象的时候调用的是无参构造方法,给comparator传的值为null.所以他会选择siftUpComparable()方法。

 offer插入元素,调用向上调整的方法时,调用siftUpComparable方法,存入的数据是按照大根堆还是小根堆的方式存储,主要是由siftUpComparable方法中调用的compareTo方法决定。

这里以Student对象为例说明。以年龄比较

2、自己创建一个比较器类,实现Comparator接口,重写compare方法,可以根据自己的想法,在插入数据后,按照大根堆或者小根堆的方式存储。

当我们在插入一个整数的时候,想要建成大根堆,但是在Integer类当中comparator方法源码的源码已经写死了,想要建立大根堆,我们就得写一个比较器,重写comparator方法。将比较器传给priorityQueue对象。

 

 接下来,步骤就和上边的类似,走到siftUp时,因为给了比较器,comparator不为空,所以进入siftUpUsingComparator方法中。使用自己写的比较器去比较。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/622732
推荐阅读
相关标签
  

闽ICP备14008679号