devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：小小林熬夜学编程 | 2024-05-25 16:09:10

赞

踩

堆数据结构

目录

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.     //向下调整，传父亲结点的下标，和每课树的结束下标
  23.     private void shiftDown(int parent,int len){
  24.         int child = 2*parent+1;
  25.         //最起码 要有左孩子，左孩子结点下标小于数组长度
  26.         while(child < len){
  27.             //一定是有有孩子的情况，这样才能找到左右孩子结点的最大值。
  28.             if(child+1<len && elem[child] < elem[child+1]){//如果有孩子结点大于左孩子结点，那么孩子结点的下标++，保证child下标一定是左右孩子最大值的下标
  29.                 child++;
  30.             }
  31.             //比较最大孩子结点与父亲结点的值，最大值放到父亲结点的位置。
  32.             if(elem[child] > elem[parent]){
  33.                 int tmp =elem[child];
  34.                 elem[child] = elem[parent];
  35.                 elem[parent] = tmp;
  36.                 parent = child;//交换完成之后，父节点指向其左孩子结点
  37.                 child = 2*parent+1;//child指向子树的孩子结点，通过循环，将子树建成堆
  38.             }else{//如果最大孩子结点的值比父亲结点的值小，则直接结束。
  39.                 break;
  40.             }
  41.         }
  42.     }
  43. }

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

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

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

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

2.4、堆的插入与删除

2.4.1、堆的插入

堆的插入需要两个步骤：

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

  

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

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

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

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

2.4.3、堆的删除

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

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

 代码示例：

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

3、优先级队列常用接口

3.1、priorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，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
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号