二叉堆
首先，看一下百度百科的完全二叉树的定义。
完全二叉树：设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
从图上看，一棵完全二叉树可能是这个样子：
注意到一个完全二叉树不一定是一个满二叉树，但是一个满二叉树一定是一个完全二叉树。
二叉堆：二叉堆的本质是一个棵完全二叉树的顺序存储。 若将List[0, 1, ..., n - 1]表示一个完全二叉树的顺序存储模式，则父节点的List下标和孩子节点的List下标之间存在下面的关系：
对于一个任意List下标为i的树节点，它的：
(1) 父节点：parent(i) = i == 0 ? null : (i - 1) / 2
(2) 左孩子：leftchild(i) = 2 * i + 1
右孩子：rightchild(i) = 2 * i + 2
大根堆：若一个二叉堆的任意一个节点i的值都大于等于其左右孩子节点(如果有的话)的值，则称其为大根堆。
给出一个list[0,...,n-1]，长度为n
2*i+1 < len && list[i]>=list[2*i+1] &&
2*i+2 < len && list[i]>=list[2*i+2]
小根堆：若一个二叉堆的任意一个节点i的值都小于等于其左右孩子节点(如果有的话)的值，则称其为小根堆。
给出一个list[0,...,n-1]，长度为n
2*i+1 < len && list[i]<=list[2*i+1] &&
2*i+2 < len && list[i]<=list[2*i+2]
代码
private int getLeftChildIndex(int root) {
return root * 2 + 1;
}
private int getRightChildIndex(int root) {
return root * 2 + 2;
}
private int getParentIndex(int root) {
if (root == 0) {
throw new UnsupportedOperationException("0 doest't have a parent node");
}
return (root - 1) / 2;
}
我们以大根堆为例来介绍建堆 ，堆排序以及优先队列的一系列操作。
大根堆
给定一组数字List[0, 1, ..., n - 1]，如何创建一个大根推呢？构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次进行合法化(上浮或下沉)让List[i]的值在最大堆中逐级下降，通过合法化操作来使得原来无序的完全二叉树满足大根堆的性质。那么，首先便要介绍这个上浮操作，在大根堆实现中，称为maxHeapify。
maxHeapify
我们给出下面这样一个例子，假设现在要对1这个节点进行maxHeapify操作来调整。由于大根堆要求任意一个节点i的值都大于等于其左右孩子节点，那么很显然的我们想到将1和其左右孩子节点中的最大值进行替换。调整完后，这个下标节点相对于其孩子节点来说便满足了大根堆的性质。但是与孩子节点交换之后，交换后的孩子节点可能会不满足大根堆性质，所以要进一步maxHeapify交换后的孩子节点。
时间复杂度
截取自算法导论的描述，对于一棵以i为根节点、大小为n的子树，其maxHeapify的时间复杂度为O(lgn)，也就是说，对于一个树高为h的节点来说，maxHeapify的时间复杂度为O(h)
代码
/**
* 从下标为root的节点进行maxHeapify
*/
private void maxHeapify(int root, int size) {
int left = getLeftChildIndex(root);
int right = getRightChildIndex(root);
int max = root;
if (left < size && list.get(left) > list.get(root)) {
max = left;
}
if (right < size && list.get(right) > list.get(max)) {
max = right;
}
if (root != max) {
swap(root, max);
maxHeapify(max, size);
}
}
buildMaxHeap
最大堆建堆，根据完全二叉树的性质，叶子节点比内部节点个数多1，所以 n/2 - 1 ~ 0 进行maxHeapify(从最后一个非叶子节点往前进行maxheapify)。
时间复杂度 截取自算法导论的描述，buildMaxHeap的时间复杂度为O(n)，也就是说，可以在线性时间内，把一个无序数组或者列表构造成一个大根堆。
代码
/**
* 建立大根堆，线性时间复杂度O(n)
*/
public void buildMaxHeap() {
int size = list.size();
for (int i = size / 2 - 1; i >= 0; i--) {
maxHeapify(i, size);
}
}
堆排序
基于上面的叙述，在将把一个无序数组或者列表构造成一个大根堆后。列表中最大的元素总在根节点List[0]中，通过把它和List[n-1]进行互换，我们可以把该元素放到排序的正确位置上。这时候。如果我们从大根堆中去掉List[n-1]（可以通过减少大根堆的size来进行），剩余的节点中，原来根节点的孩子节点List[1]...List[n-2]仍然是大根堆。而新的List[0]节点可能会违反大根堆的性质，于是我们便要进行maxHeapify(0, size-1)，从而在List[0,...,n-1]上重新构造一个大根堆。不端重复这个过程，直到堆的大小降到1。这个时候，列表中的元素便已经是排序好的元素了。
时间复杂度
堆排序的时间复杂度为O(nlogn)，O(n)次调用maxHeapify，每次调用maxHeapify的时间复杂度为O(logn)。
代码
/**
* 堆排序时间复杂度O(nlogn)
*/
public void heapSort() {
buildMaxHeap();
for (int i = list.size() - 1; i >= 1; i--) {
swap(0, i);
maxHeapify(0, i);
}
}
优先队列
基于二叉堆，有一个非常常见的应用：优先队列。这里，我们主要介绍如何基于最大堆实现最大优先队列。这里介绍下优先队列的定义， 优先队列是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字。一个最大优先队列支持以下操作：
- IncreaseKey(S,x,k): 将元素x的关键字值增加到k，同时保持大根堆性质(最大优先队列)。这里假设k的值不小于x的原始关键字值。
- Insert(S, x): 把元素x插入到集合S中，同时保持大根堆性质(最大优先队列)。
- Maximum(S): 返回S中具有最大关键字的元素（优先级最高）。
- ExtractMax(S): 去掉并返回S中具有最大关键字的元素(优先级最高)。
increaseKey
increaseKey操作是将元素List[i]的关键字值增加，这样的话List[i]相对于其父节点可能会违反最大堆的性质。一旦发现破坏性质的值，就进行上浮操作。由于上浮之后，仍然可能会违反最大堆性质。于是，这个过程需要不断的重复。时间复杂度：O(logn)。
/**
* 将下标为i的节点元素的值提升到key，需要保证list.get(i) < key
*/
private void increaseKey(int i, int key) {
if (key < list.get(i)) {
throw new UnsupportedOperationException("new key should be larger than the current key");
}
list.set(i, key);
while (i > 0 && list.get(getParentIndex(i)) < list.get(i)) {
swap(i, getParentIndex(i));
i = getParentIndex(i);
}
}
private void swap(int i, int j) {
int temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
insert
insert操作就是往优先队列中加入一个元素并维持大根堆（最大优先队列）的性质。这里我们基于increaseKey操作实现这个功能。做法就比较简单：在大根堆列表尾加入一个MIN_VALUE元素，然后将其值increaseKey到指定元素值。时间复杂度：O(logn)。
/**
* 大根推插入一个元素并维持大根堆属性
*/
public void insert(int val) {
list.add(Integer.MIN_VALUE);
increaseKey(list.size() - 1, val);
}
maximum
这个操作就比较简单了，我们直接返回List[0]即大根堆中最大元素，最大优先级队列中优先级最高的元素。时间复杂：O(1)
public int peekMax() {
if (list.size() < 1) {
throw new UnsupportedOperationException("size of maxHeap is less than 1~");
}
return list.get(0);
}
extractMax
这个操作实现思路参考堆排序过程，先将List[0]与List[n-1]交换，然后将List[n-1]从列表中移除，最后对List[0]进行maxHeapify操作。时间复杂度：O(logn)。
public int popMax() {
if (list.size() < 1) {
throw new UnsupportedOperationException("size of maxHeap is less than 1~");
}
int max = list.get(0);
swap(0, list.size() - 1);
list.remove(list.size() - 1);
maxHeapify(0, list.size());
return max;
}
完整代码
/**
* 1. 创建二叉树
* 若list[0,...,n-1]表示一个完全二叉树的顺序存储模式，则双亲节点List下标和孩子节点List下标之间的内在关系如下：
* 对于一个任意下标节点 i:
* (1) 父节点： i == 0 ? null : (i-1)/2
* (2) 左孩子: 2*i + 1
* 右孩子: 2*i + 2
* <p>
* 2. 大根堆定义：父节点的值 >= 其孩子节点的值
* list(i) >= list(2*i+1) && list(i) >= list(2*i+2)
* 小根堆定义同理
* <p>
* 3. 最大堆建堆，根据满二叉树的性质，叶子节点比内部节点个数多1，所以 n/2 - 1 ~ 0 进行maxHeapify
*/
public class MaxHeap {
private List<Integer> list;
public MaxHeap(List<Integer> list) {
this.list = new ArrayList<>(list);
}
/**
* 堆排序时间复杂度O(nlogn)
*/
public void heapSort() {
buildMaxHeap();
for (int i = list.size() - 1; i >= 1; i--) {
swap(0, i);
maxHeapify(0, i);
}
}
/**
* 建立大根堆，线性时间复杂度O(n)
*/
public void buildMaxHeap() {
int size = list.size();
for (int i = size / 2 - 1; i >= 0; i--) {
maxHeapify(i, size);
}
}
/**
* 从下标为root的节点进行maxHeapify，时间复杂度O(logn)
*/
private void maxHeapify(int root, int size) {
int left = getLeftChildIndex(root);
int right = getRightChildIndex(root);
int max = root;
if (left < size && list.get(left) > list.get(root)) {
max = left;
}
if (right < size && list.get(right) > list.get(max)) {
max = right;
}
if (root != max) {
swap(root, max);
maxHeapify(max, size);
}
}
public int popMax() {
if (list.size() < 1) {
throw new UnsupportedOperationException("size of maxHeap is less than 1~");
}
int max = list.get(0);
swap(0, list.size() - 1);
list.remove(list.size() - 1);
maxHeapify(0, list.size());
return max;
}
public int peekMax() {
if (list.size() < 1) {
throw new UnsupportedOperationException("size of maxHeap is less than 1~");
}
return list.get(0);
}
/**
* 将下标为i的节点元素的值提升到key，需要保证list.get(i) < key
*/
private void increaseKey(int i, int key) {
if (key < list.get(i)) {
throw new UnsupportedOperationException("new key should be larger than the current key");
}
list.set(i, key);
while (i > 0 && list.get(getParentIndex(i)) < list.get(i)) {
swap(i, getParentIndex(i));
i = getParentIndex(i);
}
}
private void swap(int i, int j) {
int temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
/**
* 大根推插入一个元素并维持大根堆属性
*/
public void insert(int val) {
list.add(Integer.MIN_VALUE);
increaseKey(list.size() - 1, val);
}
private int getLeftChildIndex(int root) {
return root * 2 + 1;
}
private int getRightChildIndex(int root) {
return root * 2 + 2;
}
private int getParentIndex(int root) {
if (root == 0) {
throw new UnsupportedOperationException("0 doest't have a parent node");
}
return (root - 1) / 2;
}
public List<Integer> getList() {
return list;
}
}
一些测试用例
@Test
public void testCase01() {
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 5, 4));
MaxHeap maxHeap = new MaxHeap(list);
maxHeap.heapSort();
System.out.println(maxHeap.getList()); // 1, 3, 4, 5
}
@Test
public void testCase02() {
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 5, 4, 2));
MaxHeap maxHeap = new MaxHeap(list);
maxHeap.buildMaxHeap();
int max = maxHeap.popMax();
System.out.println(max); // 5
System.out.println(maxHeap.getList()); // 4, 2, 3, 1
}
@Test
public void testCase03() {
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 5, 4));
MaxHeap maxHeap = new MaxHeap(list);
maxHeap.buildMaxHeap();
maxHeap.insert(11);
System.out.println(maxHeap.getList()); // 11, 5, 3, 1, 4
}
Java优先级队列PriorityQueue
JDK工具类中其实已经有了 我们上面实现的那个优先队列：PriorityQueue。
- PriorityQueue 是基于二叉堆实现的一个无界队列
- PriorityQueue 支持默认的自然顺序或者是自定义的排序逻辑
- PriorityQueue 不允许空值，而且不支持 non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用 Java Comparable 和 Comparator 接口给对象排序，并且在排序时会按照优先级处理其中的元素。
- PriorityQueue 是非线程安全的，所以 Java 提供了 PriorityBlockingQueue（实现 BlockingQueue接口）用于Java 多线程环境。
下面给出一个Demo，可以发现这个PriorityQueue和我上面实现的优先队列功能差不多。至此，我们便手写了一个JDK源码里面的优先队列。
public static void main(String[] args) {
Queue<Integer> queue1 = new PriorityQueue<Integer>();
queue1.add(2);
queue1.add(1);
queue1.add(3);
while (!queue1.isEmpty()) {
Integer i = queue1.poll();
System.out.println(i);
}
Comparator<Student> comparator = Comparator.comparingInt(o -> o.id);
Queue<Student> queue2 = new PriorityQueue<Student>(comparator);
queue2.add(new Student(2, "B"));
queue2.add(new Student(1, "A"));
queue2.add(new Student(3, "C"));
while (!queue2.isEmpty()) {
Student s = queue2.poll();
System.out.println(s.toString());
}
}
public static class Student {
private int id;
private String name;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
public String toString() {
return id + "-" + name;
}
}
