数据布局 堆与优先级队列

📕1. 堆(Heap)

✏️1.1 堆的概念

堆（Heap）是一种特殊的完全二叉树，它满足父节点的值总是不大于或不小于其子节点的值。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆满足以下两个性子:
1.堆中某个节点的值总是不大于或不小于其根节点的值
2. 堆总是一棵完全二叉树

✏️1.2 堆的存储方式

从堆的概念可知,堆是一颗完全二叉树,因此可以层序的规则接纳顺序的方式来高效存储
对与非完全二叉树,则不适合使用顺序的方式举行存储,因为为了能够还原二叉树,空间中必须要存储空节点,这会导致空间使用率比较低.

将元素存储到数组中后,假设i为节点在数组中的下标,则有:

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

✏️1.3 堆的创建

想要创建堆,我们起首要了解向下调整(这里以创建小根堆为例):

• 我们将想要调整的节点标记为parent,child为该节点的左孩子(假如有孩子节点,则一定是现有左孩子)
  
• 假如有左孩子节点,则判断child<size(数组元素个数),然后举行以下操作,直到child<size条件不成立
  2.1 判断parent的右孩子是否存在,找到左右孩子中最小的那个,用child标记.(假如右孩子比左孩子小,child+=1)
  2.2 将parent与child比较,假如parent<child,则调整结束;否则举行元素交换,交换完之后,有可能新构建的子树又不满足小根堆,所以需要将parent = child,child = parent * 2 + 1. 然后继续重复2操作.这便是向下调整.
  

1.     public void siftDown(int[] arr,int parent){
2.         //此时child标记的左孩子,因为parent右孩子结点的话只能先有左孩子
3.         int child = parent * 2 + 1;
4.         int size = arr.length;
5.         while(child < size){
6.             // 如果右孩⼦存在，找到左右孩⼦中较⼩的孩⼦,⽤child进⾏标记
7.             if (child+1 < size && arr[child] < arr[child+1]){
8.                 child+=1;
9.             }
10.             // 如果双亲⽐其最⼩的孩⼦还⼩，说明该结构已经满⾜堆的特性了
11.             if (arr[parent] <= arr[child]){
12.                 break;
13.             }else {
14.                 // 将双亲与较⼩的孩⼦交换
15.                 int t = arr[parent];
16.                 arr[parent] = arr[child];
17.                 arr[child] = t;
18.                 // parent中⼤的元素往下移动，可能会造成⼦树不满⾜堆的性质，因此需要继续向下调整
19.                 parent = child;
20.                 child = parent * 2 + 1;
21.             }
22.         }
23.     }

复制代码

了解完向下调整,那给你任意一些数据,那我们该如何创建成小根堆呢?

1. public void createHeap(int[] arr){
2.         // 找倒数第⼀个⾮叶⼦节点，从该节点位置开始往前⼀直到根节点，遇到⼀个节点，应⽤向下调整
3.         int root = (arr.length-2)/2;
4.         for (; root >= 0 ; root--) {
5.                 siftDown(arr,root);
6.         }
7. }

复制代码

还需要注意的是,建堆的时间复杂度为O(N);
✏️1.4 堆的插入

堆的插入统共需要两个步骤;

• 先将元素放入到数组末了一个空间中(数组长度不够时需要扩容)
  
• 将新插入的节点使用向上调整,直到满足堆的性子
  

向上调整:

1. public void siftUp(int child){
2.         //以创建小根堆为例
3.         //找到child的根节点
4.         int parent = (child-1)/2;
6.         while(child > 0){
7.             // 如果双亲⽐孩⼦小，parent满⾜堆的性质，调整结束
8.             if (arr[parent] < arr[child]){
9.                 break;
10.             }else {
11.                 // 将双亲与孩⼦节点进⾏交换
12.                int tmp = arr[parent];
13.                arr[parent] = arr[child];
14.                arr[child] = arr[tmp];
15.             }
17.             // ⼩的元素向下移动，调整后的⼦树可能不满⾜堆的性质，因此需要继续向上调增
18.             child = parent;
19.             parent = (child-1)/2;
20.         }
21.     }

复制代码

插入数据:

1. /**
2. * 插入数据：
3. * 每次插入到当前堆的最后一个(数组的最后一个)，然后向上调整
4. */
5.     public void offer(int val) {
6.         if(isFull()) {
7.             elem = Arrays.copyOf(elem,2*elem.length);
8.         }
9.         elem[size] = val;
10.         //调整
11.         siftUp(size);
12.         size++;
13.     }

复制代码

✏️1.5 堆的删除

堆的插入统共需要两个步骤;

• 将堆顶元素与堆中末了一个元素交换
  
• 将对中有效数据减少一个
  
• 对堆顶元素举行向下调整
  

注意：堆的删除⼀定删除的是堆顶元素
📕2. 优先级队列(PriorityQueue)

之前我们已经学习过队列了,队列是一种先辈先出(FIFO)的数据布局,但有些环境下，操作的数据可能带有优先级,出队列时，可能需要优先级高的元素先出队列 . 好比：在手机上玩游戏的时候，假如有来电，那么体系应该优先处理打进来的电话.该场景下，使用队列显然不符合，因此数据布局应该提供两个最基本的操作，一个是返回最高优先级对象，⼀个是添加新的对象。这种数据布局就是优先级队列(PriorityQueue).
✏️2.1 堆与优先级队列的关系

起首各人要知道一点 , 堆是一种数据布局 , 而优先级队列也是一种数据布局 , 二者是完全单独且不同的数据布局.
优先队列本身就是一种数据布局，它的偏重点是优先，而不是队列。优先是目标，队列只是形式.
优先级队列不光可以用堆来实现 , 用链表也是可以模拟实现的 , 只不过在JDK1.8中 , PriorityQueue的底层实现使用了堆这种数据布局.
✏️2.2 优先级队列的构造方法

注意：默认环境下，PriorityQueue队列是小堆，假如需要大堆需要用户提供比较器
✏️2.3 优先级队列的常用方法

优先级队列的扩容说明：
• 假如容量小于64时，是按照oldCapacity的2倍方式扩容的
• 假如容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
• 假如容量凌驾MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来举行扩容
3. Java对象的比较

在SE阶段中,我们介绍了引用范例变量使用equals()方法举行比较 , 基本数据范例变量使用大于号小于号举行比较 , 故以上两种方法此处不再赘述.
3.1 基于Comparble接口类的比较

Comparble是JDK提供的泛型的比较接口类，源码实现详细如下：

1. public interface Comparable<E> {
2.         // 返回值:
3.         // < 0: 表⽰ this 指向的对象⼩于 o 指向的对象
4.         // == 0: 表⽰ this 指向的对象等于 o 指向的对象
5.         // > 0: 表⽰ this 指向的对象⼤于 o 指向的对象
6.         int compareTo(E o);
7. }

复制代码

对于用户定义范例，假如要想按照大小的方式举行比较时：
在定义类时，实现Comparble接口即可，然后在类中重写compareTo方法。

1. public class Card implements Comparable<Card> {
3.         public int rank; // 数值
4.         public String suit; // 花⾊
5.        
6.         public Card(int rank, String suit) {
7.                 this.rank = rank;
8.                 this.suit = suit;
9.         }
10.         // 根据数值⽐较，不管花⾊
11.         // 这⾥我们认为 null 是最⼩的
12.        
13.         @Override
14.         public int compareTo(Card o) {
15.                 if (o == null) {
16.                         return 1;
17.                 }
18.                 return this.rank - o.rank;
19.         }
20.        
21.         public static void main(String[] args){
22.                 Card p = new Card(1, "♠");
23.                 Card q = new Card(2, "♠");
24.                 Card o = new Card(1, "♠");
25.                 System.out.println(p.compareTo(o)); // == 0，表⽰牌相等
26.                 System.out.println(p.compareTo(q)); // < 0，表⽰ p ⽐较⼩
27.                 System.out.println(q.compareTo(p)); // > 0，表⽰ q ⽐较⼤
28.         }
29. }

复制代码

3.2 基于比较器比较

Comparator是java.util 包中的泛型接口类 , 源码如下:

1. public interface Comparator<T> {
2.         // 返回值:
3.         // < 0: 表⽰ o1 指向的对象⼩于 o2 指向的对象
4.         // == 0: 表⽰ o1 指向的对象等于 o2 指向的对象
5.         // > 0: 表⽰ o1 指向的对象等于 o2 指向的对象
6.         int compare(T o1, T o2);
7. }

复制代码

按照比较器方式举行比较，详细步骤如下：

• 用户自定义比较器类，实现Comparator接口
  
• 重写Comparator中的compare方法
  

1. import java.util.Comparator;
3. class Card {
4.         public int rank; // 数值
5.         public String suit; // 花⾊
6.        
7.         public Card(int rank, String suit) {
8.                 this.rank = rank;
9.                 this.suit = suit;
10.         }
11. }
13. class CardComparator implements Comparator<Card> {
14.         // 根据数值⽐较，不管花⾊
15.         // 这⾥我们认为 null 是最⼩的
16.        
17.         @Override
18.         public int compare(Card o1, Card o2) {
19.                 if (o1 == o2) {
20.                         return 0;
21.                 }
22.                 if (o1 == null) {
23.                         return -1;
24.                 }
25.                 if (o2 == null) {
26.                         return 1;
27.                 }
28.                 return o1.rank - o2.rank;
29.         }
31.         public static void main(String[] args){
32.                 Card p = new Card(1, "♠");
33.                 Card q = new Card(2, "♠");
34.                 Card o = new Card(1, "♠");
35.                 // 定义⽐较器对象
36.                 CardComparator cmptor = new CardComparator();
37.                 // 使⽤⽐较器对象进⾏⽐较
38.                 System.out.println(cmptor.compare(p, o)); // == 0，表⽰牌相等
39.                 System.out.println(cmptor.compare(p, q)); // < 0，表⽰ p ⽐较⼩
40.                 System.out.println(cmptor.compare(q, p)); // > 0，表⽰ q ⽐较⼤
41.         }
42. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告