数据结构 - 6（优先级队列（堆）13000字详解）

一：堆

1.1 堆的基本概念

堆分为两种：大堆和小堆。它们之间的区别在于元素在堆中的排列顺序和访问方式。

1. 大堆（Max Heap）：
   在大堆中，父节点的值比它的子节点的值要大。也就是说，堆的根节点是堆中最大的元素。大堆被用于实现优先级队列，其中根节点的元素始终是队列中最大的元素。大堆可以通过以下特点来进行维护：

• 对于每个父节点，它的值大于或等于其子节点的值。

2. 小堆（Min Heap）：
   在小堆中，父节点的值比它的子节点的值要小。也就是说，堆的根节点是堆中最小的元素。小堆常用于实现优先级队列，其中根节点的元素始终是队列中最小的元素。小堆可以通过以下特点来进行维护：

• 对于每个父节点，它的值小于或等于其子节点的值。

以下是一个示例图示，展示了一个包含7个元素的大堆和小堆的结构：

大堆：90/    \75      30/  \    /  \20   15  10   7小堆：7/   \10     30/  \   /  \20   15 75  90

这些图示说明了大堆和小堆的不同排列顺序。在大堆中，父节点的值大于子节点的值，而在小堆中，父节点的值小于子节点的值。

注意：堆总是一颗完全二叉树

1.2堆的存储方式

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

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

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

• 如果i为0，则i表示的节点为根节点
• 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
• 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

1.3 堆的下沉

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

仔细观察上图后发现：根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可。

下面是代码实现：

// shiftDown方法用来实现下沉操作
// array参数是待构建小堆的数组
// parent参数是当前需要下沉的节点的索引
public void shiftDown(int[] array, int parent) {int length = array.length;int child = 2 * parent + 1; // 左子节点索引while (child < length) {// 找到左右孩子中较小的孩子if (child + 1 < length && array[child] > array[child + 1]) {child++; // 如果右子节点存在并且小于左子节点的值，则将child指向右子节点}// 如果当前节点小于或等于左右子节点中较小的节点，说明已经符合小堆要求if (array[parent] <= array[child]) {break;}// 否则，交换当前节点和较小子节点的值，接着需要继续向下调整int temp = array[parent];array[parent] = array[child];array[child] = temp;parent = child;child = 2 * parent + 1;}
}

这段代码实现了堆排序中的下沉操作（也称为向下调整或堆化）。下沉操作用于维护小堆的性质，确保父节点永远小于或等于其子节点。

时间复杂度分析：
最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O（log n）

1.4 堆的创建

那对于普通的序列{ 1,5,3,8,7,6 }，即根节点的左右子树不满足堆的特性，又该如何调整呢？

参考代码：

public static void createHeap(int[] array) {// 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整int root = ((array.length-2)>>1);for (; root >= 0; root--) {shiftDown(array, root);}
}

1.5建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

因此：建堆的时间复杂度为O(N)。

1.6堆的插入和删除

1.6.1 堆的插入

堆的插入总共需要两个步骤：

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

下面是堆的删除操作的代码实现，包含详细注释：

public void shiftUp(int child) {// 找到child的双亲int parent = (child - 1) / 2;while (child > 0) {// 如果双亲比孩子大，parent满足堆的性质，调整结束if (array[parent] > array[child]) {break;}else{// 将双亲与孩子节点进行交换int t = array[parent];array[parent] = array[child];array[child] = t;// 小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增child = parent;parent = (child - 1) / 1;}}
}

1.6.2 堆的删除

注意：堆的删除一定删除的是堆顶元素。具体如下：

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

下面是堆的删除操作的代码实现，包含详细注释：

public void deleteTop() {// 将堆顶元素与堆中最后一个元素交换array[0] = array[size - 1];// 堆中有效数据个数减少一个size--;// 对堆顶元素进行向下调整int parent = 0; // 当前节点的索引// 持续向下调整，直到满足堆的性质while (true) {// 左孩子节点的索引int leftChild = parent * 2 + 1;// 右孩子节点的索引int rightChild = leftChild + 1;// 父节点与左右孩子节点中值最大的节点进行交换int maxChild = parent; // 最大值节点的索引// 如果左孩子存在且大于父节点，则更新最大值节点if (leftChild < size && array[leftChild] > array[maxChild]) {maxChild = leftChild;}// 如果右孩子存在且大于当前最大值节点，则更新最大值节点if (rightChild < size && array[rightChild] > array[maxChild]) {maxChild = rightChild;}// 如果最大值节点是当前节点本身，则调整结束 if (maxChild == parent) {break;} else {// 交换最大节点与父节点int temp = array[parent];array[parent] = array[maxChild];array[maxChild] = temp;// 更新当前节点为最大值节点parent = maxChild;}}
}

二：优先级队列

2.1 概念

前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。

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

2.2堆的使用

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。

关于PriorityQueue的使用要注意：

1. 使用时必须导入PriorityQueue所在的包，即：
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出
   ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素

PriorityQueue中常见的构造方法：

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

下面是使用示例：

static void TestPriorityQueue(){// 创建一个空的优先级队列，底层默认容量是11PriorityQueue<Integer> q1 = new PriorityQueue<>();// 创建一个空的优先级队列，底层的容量为initialCapacityPriorityQueue<Integer> q2 = new PriorityQueue<>(100);ArrayList<Integer> list = new ArrayList<>();list.add(4);list.add(3);list.add(2);list.add(1);// 用ArrayList对象来构造一个优先级队列的对象// q3中已经包含了三个元素PriorityQueue<Integer> q3 = new PriorityQueue<>(list);System.out.println(q3.size());System.out.println(q3.peek());}

注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器

// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}
public class TestPriorityQueue {public static void main(String[] args) {PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());p.offer(4);p.offer(3);p.offer(2);p.offer(1);p.offer(5);System.out.println(p.peek());}
}

下面是 PriorityQueue中常用的方法：

函数名	功能介绍
booleanoffer(E e)	插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度 ，注意：空间不够时候会进行扩容
E peek()	获取优先级最高的元素，如果优先级队列为空，返回null
E poll()	移除优先级最高的元素并返回，如果优先级队列为空，返回null
int size()	获取有效元素的个数
void clear()	清空
boolean isEmpty()	检测优先级队列是否为空，空返回true

下面是这些方法的使用示例：

import java.util.PriorityQueue;public class Main {public static void main(String[] args) {PriorityQueue<Integer> heap = new PriorityQueue<>();// 测试插入元素heap.offer(10); // 返回 trueheap.offer(5); // 返回 trueheap.offer(15); // 返回 trueheap.offer(2); // 返回 true// 测试获取优先级最高的元素// 结果为 2System.out.println(heap.peek());// 测试移除优先级最高的元素// 结果为 2System.out.println(heap.poll());// 测试获取有效元素的个数// 结果为 3System.out.println(heap.size());// 测试清空优先级队列heap.clear();// 测试检测优先级队列是否为空// 结果为 trueSystem.out.println(heap.isEmpty());}
}

以下是JDK 1.8中，PriorityQueue的扩容方式：

优先级队列的扩容说明：

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

MAX_ARRAY_SIZE等于Integer.MAX_VALUE - 8，Integer.MAX_VALUE - 8。等于 2,147,483,639。

2.3 用堆模拟实现优先级队列

我们通过堆可以模拟实现优先级队列，因为堆具有以下特性：

1. 大堆或小堆：堆可以是大堆或小堆，其中大堆意味着父节点的值大于或等于其子节点的值，而小堆意味着父节点的值小于或等于其子节点的值。
2. 优先级定义：我们可以将堆中的元素与优先级相关联。较高的优先级可以根据堆类型来确定是最大值还是最小值。

优先性在优先级队列中体现在以下方面：

1. 插入元素：由于堆的性质，插入的元素会按照其优先级找到正确的位置插入。较高优先级的元素会被放置在堆的顶部（根节点）。
2. 删除元素：从堆中删除元素时，会删除具有最高（最大堆）或最低（最小堆）优先级的元素。这样，每次删除的元素都是具有最高/最低优先级的元素。

通过以上方式，可以使用堆来实现优先级队列，确保具有更高优先级的元素优先被处理或删除。

下面我们基于堆来模拟实现一个优先级队列：

public class MyPriorityQueue {// 演示作用，不再考虑扩容部分的代码private int[] array = new int[100];  // 使用数组来存储元素private int size = 0;  // 当前队列的大小// 向优先队列中插入元素public void offer(int e) {array[size++] = e;  // 将元素插入数组末尾shiftUp(size - 1);  // 对插入的元素进行上浮操作，以保持堆的性质}// 弹出并返回优先队列中最高优先级的元素public int poll() {int oldValue = array[0];  // 保存堆顶元素的值array[0] = array[--size];  // 将堆尾元素移到堆顶shiftDown(0);  // 对堆顶元素进行下沉操作，以保持堆的性质return oldValue;  // 返回弹出的元素值}// 返回优先队列中最高优先级的元素public int peek() {return array[0];  // 直接返回堆顶元素的值}
}

请注意，此处的代码仅展示了演示目的，没有考虑扩容部分的代码实现。

三： 堆的应用

3.1PriorityQueue的实现

用堆作为底层结构封装优先级队列，这点我们已经讲过，在此不过多赘述

3.2堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

3.3Top-k问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
我们可以通过使用堆来解决TOP-K问题，具体步骤如下：

一： 创建一个大小为K的最小堆（或最大堆，取决于你是求前K个最小值还是最大值）。
二：遍历数据集合，对于每个元素执行以下操作：

• 如果堆的大小小于K，将当前元素插入堆中。
• 如果堆的大小等于K，比较当前元素与堆顶元素的大小
• 如果当前元素大于堆顶元素（最小堆），将堆顶元素弹出，将当前元素插入堆中。
• 如果当前元素小于堆顶元素（最大堆），跳过当前元素。

三： 遍历完数据集合后，堆中的元素即为前K个最小（或最大）的元素。

下面是一个使用Java实现堆解决TOP-K问题的示例代码：

import java.util.PriorityQueue;public class TopK {public static void main(String[] args) {int[] nums = {9, 3, 7, 5, 1, 8, 2, 6, 4};int k = 4;findTopK(nums, k);}private static void findTopK(int[] nums, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>();for (int num : nums) {if (minHeap.size() < k) {minHeap.offer(num);} else if (num > minHeap.peek()) {minHeap.poll();minHeap.offer(num);}}System.out.println("Top " + k + " elements:");while (!minHeap.isEmpty()) {System.out.print(minHeap.poll() + " ");}}
}

以上示例中，对数组nums求前4个最小元素，使用了PriorityQueue实现了一个小顶堆。遍历数组时，根据堆的大小和当前元素与堆顶元素的比较进行插入和调整。最后，打印出堆中的元素即为前4个最小的元素。

四：java对象的比较

4.1PriorityQueue中插入对象

优先级队列在插入元素时有个要求：插入的元素不能是null或者元素之间必须要能够进行比较，为了简单起见，我们只是插入了Integer类型，那优先级队列中能否插入自定义类型对象呢？

class Card {public int rank; // 数值public String suit; // 花色public Card(int rank, String suit) {this.rank = rank;this.suit = suit;}
}
public class TestPriorityQueue {public static void TestPriorityQueue(){PriorityQueue<Card> p = new PriorityQueue<>();p.offer(new Card(1, "♠"));p.offer(new Card(2, "♠"));}public static void main(String[] args) {TestPriorityQueue();}
}

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

4.2 元素的比较

4.2.1基本元素的比较

在Java中，基本类型的对象可以直接比较大小。

public class TestCompare {public static void main(String[] args) {int a = 10;int b = 20;System.out.println(a > b);System.out.println(a < b);System.out.println(a == b);char c1 = 'A';char c2 = 'B';System.out.println(c1 > c2);System.out.println(c1 < c2);System.out.println(c1 == c2);boolean b1 = true;boolean b2 = false;System.out.println(b1 == b2);System.out.println(b1 != b2);}
}

4.2.2 对象比较的问题

4.2.2.1equals

class Card {public int rank; // 数值public String suit; // 花色public Card(int rank, String suit) {this.rank = rank;this.suit = suit;}
}
public class TestPriorityQueue {public static void main(String[] args) {Card c1 = new Card(1, "♠");Card c2 = new Card(2, "♠");Card c3 = c1;//System.out.println(c1 > c2);  // 编译报错System.out.println(c1 == c2);  // 编译成功 ----> 打印false，因为c1和c2指向的是不同对象//System.out.println(c1 < c2);  // 编译报错System.out.println(c1 == c3);  // 编译成功 ----> 打印true，因为c1和c3指向的是同一个对象}
}

c1、c2和c3分别是Card类型的引用变量，上述代码在比较编译时：

• c1 > c2 编译失败
• c1== c2 编译成功
• c1 < c2 编译失败

从编译结果可以看出，Java中引用类型的变量不能直接按照 > 或者 < 方式进行比较。 那为什么== 可以比较？

因为：对于用户实现自定义类型，都默认继承自Object类，而Object类中提供了equal方法，而==默认情况下调用的就是equal方法，但是该方法的比较规则是：没有比较引用变量引用对象的内容，而是直接比较引用变量的地址，但有些情况下该种比较就不符合题意。

// Object中equal的实现，可以看到：直接比较的是两个引用变量的地址
public boolean equals(Object obj) {return (this == obj);
}

有些情况下，需要比较的是对象中的内容，比如：向优先级队列中插入某个对象时，需要对按照对象中内容来调整堆，那该如何处理呢？答案是重写覆盖基类的equals

public class Card {public int rank; // 数值public String suit; // 花色public Card(int rank, String suit) {this.rank = rank;this.suit = suit;}@Overridepublic boolean equals(Object o) {// 自己和自己比较if (this == o) {return true;}// o如果是null对象，或者o不是Card的子类if (o == null || !(o instanceof Card)) {return false;}// 注意基本类型可以直接比较，但引用类型最好调用其equal方法Card c = (Card)o;return rank == c.rank&& suit.equals(c.suit);}
}

注意： 一般覆写 equals 的套路就是上面演示的

1. 如果指向同一个对象，返回 true
2. 如果传入的为 null，返回 false
3. 如果传入的对象类型不是 Card，返回 false
4. 按照类的实现目标完成比较，例如这里只要花色和数值一样，就认为是相同的牌
5. 注意下调用其他引用类型的比较也需要 equals，例如这里的 suit 的比较

覆写基类equal的方式虽然可以比较，但缺陷是：equal只能按照相等进行比较，不能按照大于、小于的方式进行比较。

4.2.2.2 Comparble接口

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

public interface Comparable<E> {// 返回值:// < 0: 表示 this 指向的对象小于 o 指向的对象// == 0: 表示 this 指向的对象等于 o 指向的对象// > 0: 表示 this 指向的对象大于 o 指向的对象int compareTo(E o);
}

对用用户自定义类型，如果要想按照大小与方式进行比较时：在定义类时，实现Comparble接口即可，然后在类中重写compareTo方法。

Java中的Comparable接口是用于实现对象的自然排序的接口。它包含一个compareTo方法，用于比较两个对象的顺序。

compareTo方法有以下三种返回值：

• 如果当前对象小于被比较对象，则返回一个负整数。
• 如果当前对象等于被比较对象，则返回0。
• 如果当前对象大于被比较对象，则返回一个正整数。

下面是一个简单的例子，演示如何使用Comparable接口来自然排序自定义的Person类：

import java.util.ArrayList;
import java.util.Collections;class Person implements Comparable<Person> {private String name;private int age;public Person(String name, int age) {this.name = name;this.age = age;}// 实现compareTo方法@Overridepublic int compareTo(Person other) {return this.age - other.age; // 按照年龄排序}// 其他getter和setter方法@Overridepublic String toString() {return "Person{" +"name='" + name + '\'' +", age=" + age +'}';}
}public class Main {public static void main(String[] args) {ArrayList<Person> people = new ArrayList<>();people.add(new Person("Alice", 25));people.add(new Person("Bob", 20));people.add(new Person("Charlie", 30));System.out.println("排序前:");for (Person person : people) {System.out.println(person);}Collections.sort(people); // 使用Collections.sort()方法进行排序时，会自动调用compareTo()方法进行比较System.out.println("排序后:");for (Person person : people) {System.out.println(person);}}
}

输出结果：

排序前:
Person{name='Alice', age=25}
Person{name='Bob', age=20}
Person{name='Charlie', age=30}
排序后:
Person{name='Bob', age=20}
Person{name='Alice', age=25}
Person{name='Charlie', age=30}

在上面的代码中，我们定义了一个Person类，并实现了Comparable接口。我们通过compareTo方法比较了两个Person对象的年龄，并在Main类中使用Collections.sort方法对people列表进行了排序。排序后，列表中的Person对象按照年龄的升序排列。

注意：Compareble是java.lang中的接口类，可以直接使用。

4.2.2.3 基于比较器比较

在Java中，如果我们想要比较两个对象，并根据它们的属性值进行排序或判断它们的相对顺序，我们可以使用比较器（Comparator）进行操作。

比较器是一个用于定义对象之间比较行为的接口。它包含了一个用于比较两个对象的方法 - compare()。该方法接受两个参数，分别是要比较的两个对象，然后返回一个整数值来表示它们的相对顺序。

下面是一个简单的示例，展示如何使用比较器比较两个Person对象：

import java.util.*;// 定义Person类
class Person {private String name;private int age;public Person(String name, int age) {this.name = name;this.age = age;}// 省略其他属性和方法public String getName() {return name;}public int getAge() {return age;}
}// 定义比较器类
class AgeComparator implements Comparator<Person> {@Overridepublic int compare(Person person1, Person person2) {if (person1.getAge() < person2.getAge()) {return -1; // person1在前} else if (person1.getAge() > person2.getAge()) {return 1; // person2在前} else {return 0; // 保持顺序不变}}
}public class Main {public static void main(String[] args) {// 创建Person对象Person person1 = new Person("Alice", 25);Person person2 = new Person("Bob", 30);Person person3 = new Person("John", 20);// 创建比较器对象AgeComparator comparator = new AgeComparator();// 使用比较器比较对象int result1 = comparator.compare(person1, person2); // 返回-1，person1在前int result2 = comparator.compare(person2, person1); // 返回1，person2在前int result3 = comparator.compare(person1, person3); // 返回0，保持顺序不变System.out.println(result1);//-1System.out.println(result2);//1System.out.println(result3);//0}
}

在上述代码中，我们定义了一个Person类，其中包含了姓名（name）和年龄（age）属性。然后，我们创建了一个比较器类AgeComparator，实现了Comparator接口，并重写了compare()方法来根据年龄来判断相对顺序。

在main()方法中，我们创建了三个Person对象，并使用AgeComparator比较器对象来比较它们的年龄。最后，我们打印了比较的结果，验证了对象之间的比较行为。

这就是基于比较器比较两个对象的示例。通过实现Comparator接口并重写compare()方法，我们可以定制化对象之间的比较行为，从而实现根据特定属性进行排序或判断相对顺序。

注意：Comparator是java.util 包中的泛型接口类，使用时必须导入对应的包。

我们要注意区分Comparable和Comparato：

• 实现Comparable接口，重写compareTo方法
• 实现Comparator接口，重写compare方法

三种比较方式对比：

覆写的方法	说明
Object.equals	因为所有类都是继承自 Object 的，所以直接覆写即可，不过只能比较相等与否
Comparable.compareTo	需要手动实现接口，侵入性比较强，但一旦实现，每次用该类都有顺序，属于内部顺序，Compareble是java.lang中的接口类，可以直接使用。
Comparator.compare	需要实现一个比较器对象，对待比较类的侵入性弱，但对算法代码实现侵入性强 ，Comparator是java.util 包中的泛型接口类，使用时必须导入对应的包。