文章标题:
数据结构里堆与优先级队列的特性剖析
文章内容:
文章目录
-
- 📕1. 堆(Heap)
-
-
- ✏️1.1 堆的概念
- ✏️1.2 堆的存储形式
- ✏️1.3 堆的构建
- ✏️1.4 堆的插入
- ✏️1.5 堆的删除
-
- 📕2. 优先级队列(PriorityQueue)
-
-
- ✏️2.1 堆和优先级队列的关联
- ✏️2.2 优先级队列的构造途径
- ✏️2.3 优先级队列的常用操作
-
- 3. Java对象的比较
-
-
- 3.1 基于Comparble接口的比较
- 3.2 基于比较器的比较
-
📕1. 堆(Heap)
✏️1.1 堆的概念
堆属于一种特殊的完全二叉树,它具备这样的特性:父节点的值要么始终不大于子节点的值,要么始终不小于子节点的值。其中,根节点最大的堆被称作最大堆或者大根堆,根节点最小的堆则叫做最小堆或者小根堆。
堆满足如下两个特性:
1. 堆中任意一个节点的值都不会大于或小于其根节点的值
2. 堆始终是一棵完全二叉树
✏️1.2 堆的存储形式
从堆的概念可知,堆是一棵完全二叉树,所以能够按照层序的规则采用顺序的方式来高效存储。
对于非完全二叉树而言,不适合运用顺序的方式进行存储,因为要还原二叉树的话,空间中得存储空节点,这会使得空间利用率比较低。
当元素存储到数组中后,假设i为节点在数组中的下标,那么有:
- 若i为0,则该节点为根节点;不然,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步骤。这就是向下调整。
public void siftDown(int[] arr, int parent) {
// 此时child标记左孩子,因为parent右孩子节点的话必然先有左孩子
int child = parent * 2 + 1;
int size = arr.length;
while (child < size) {
// 如果右孩子存在,找到左右孩子中较小的孩子,用child标记
if (child + 1 < size && arr[child] < arr[child + 1]) {
child += 1;
}
// 如果双亲比其最小的孩子还小,说明该结构已满足堆的特性
if (arr[parent] <= arr[child]) {
break;
} else {
// 将双亲与较小的孩子交换
int t = arr[parent];
arr[parent] = arr[child];
arr[child] = t;
// parent中大的元素往下移动,可能导致子树不满足堆的性质,因此需继续向下调整
parent = child;
child = parent * 2 + 1;
}
}
}
了解了向下调整后,对于任意给定的数据,该如何构建成小根堆呢?
public void createHeap(int[] arr) {
// 找到倒数第一个非叶节点,从该节点位置开始往前一直到根节点,遇到一个节点就应用向下调整
int root = (arr.length - 2) / 2;
for (; root >= 0; root--) {
siftDown(arr, root);
}
}
还需注意,建堆的时间复杂度为O(N);
✏️1.4 堆的插入
堆的插入总共分为两个步骤:
- 先把元素放到数组的最后一个空间中(数组长度不够时需要扩容)
- 利用向上调整新插入的节点,直至满足堆的特性
向上调整:
public void siftUp(int child) {
// 以创建小根堆为例
// 找到child的根节点
int parent = (child - 1) / 2;
while (child > 0) {
// 如果双亲比孩子小,parent满足堆的性质,调整结束
if (arr[parent] < arr[child]) {
break;
} else {
// 将双亲与孩子节点进行交换
int tmp = arr[parent];
arr[parent] = arr[child];
arr[child] = tmp;
}
// 小的元素向下移动,调整后的子树可能不满足堆的性质,因此需继续向上调整
child = parent;
parent = (child - 1) / 2;
}
}
插入数据:
/**
* 插入数据:
* 每次插入到当前堆的最后一个(数组的最后一个),然后向上调整
*/
public void offer(int val) {
if (isFull()) {
elem = Arrays.copyOf(elem, 2 * elem.length);
}
elem[size] = val;
// 调整
siftUp(size);
size++;
}
✏️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提供的泛型的比较接口类,源码实现具体如下:
public interface Comparable<E> {
// 返回值:
// < 0: 表示 this 指向的对象小于 o 指向的对象
// == 0: 表示 this 指向的对象等于 o 指向的对象
// > 0: 表示 this 指向的对象大于 o 指向的对象
int compareTo(E o);
}
对于用户定义类型,如果要想按照大小的方式进行比较时:
在定义类时,实现Comparble接口即可,然后在类中重写compareTo方法。
public class Card implements Comparable<Card> {
public int rank; // 数值
public String suit; // 花色
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
// 根据数值比较,不管花色
// 这里我们认为 null 是最小的
@Override
public int compareTo(Card o) {
if (o == null) {
return 1;
}
return this.rank - o.rank;
}
public static void main(String[] args) {
Card p = new Card(1, "♠");
Card q = new Card(2, "♠");
Card o = new Card(1, "♠");
System.out.println(p.compareTo(o)); // == 0,表示牌相等
System.out.println(p.compareTo(q)); // < 0,表示 p 比较小
System.out.println(q.compareTo(p)); // > 0,表示 q 比较大
}
}
3.2 基于比较器的比较
Comparator是java.util包中的泛型接口类,源码如下:
public interface Comparator<T> {
// 返回值:
// < 0: 表示 o1 指向的对象小于 o2 指向的对象
// == 0: 表示 o1 指向的对象等于 o2 指向的对象
// > 0: 表示 o1 指向的对象等于 o2 指向的对象
int compare(T o1, T o2);
}
按照比较器方式进行比较,具体步骤如下:
- 用户自定义比较器类,实现Comparator接口
- 重写Comparator中的compare方法
import java.util.Comparator;
class Card {
public int rank; // 数值
public String suit; // 花色
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
}
class CardComparator implements Comparator<Card> {
// 根据数值比较,不管花色
// 这里我们认为 null 是最小的
@Override
public int compare(Card o1, Card o2) {
if (o1 == o2) {
return 0;
}
if (o1 == null) {
return -1;
}
if (o2 == null) {
return 1;
}
return o1.rank - o2.rank;
}
public static void main(String[] args) {
Card p = new Card(1, "♠");
Card q = new Card(2, "♠");
Card o = new Card(1, "♠");
// 定义比较器对象
CardComparator cmptor = new CardComparator();
// 使用比较器对象进行比较
System.out.println(cmptor.compare(p, o)); // == 0,表示牌相等
System.out.println(cmptor.compare(p, q)); // < 0,表示 p 比较小
System.out.println(cmptor.compare(q, p)); // > 0,表示 q 比较大
}
}
文章整理自互联网,只做测试使用。发布者:Lomu,转转请注明出处:https://www.it1024doc.com/12849.html