一、二叉堆
1、什么问题使用动态数组、有序动态数组、红黑树都不能很好的解决，而需要使用二叉堆？
- Top K 的问题(查找或者删除最大值)
- 动态数组：查O(n)、删O(n)、增O(1)
- 有序动态数组：查O(1)、删O(1)、增O(n)
- 红黑树：查O(logn)、删O(logn)、增O(logn)
- 二叉堆：查O(1)、删O(logn)、增O(logn)
image.png
2、什么是 Top K 问题？
- 从海量数据中找出前 K 个数据
- 比如从 100 万个整数中找出最大的 100 个整数
- Top K 问题的经典解法之一：可以用数据结构
二叉堆来解决
3、什么是二叉堆？
-
二叉堆(Binary Heap)：的逻辑结构就是一棵完全二叉树，所以也叫做完全二叉堆
image.png
4、二叉堆和堆空间有什么区别？
-
二叉堆：是一种树状的数据结构， -
堆空间：是内存模型
image.png
5、最大堆的添加流程（简单但是最重要，学会画图分析）？
image.png
image.png
6、最大堆的删除流程（简单但是最重要，学会画图分析）？
image.png
image.png
7、最大堆删除和添加流程中，对交互代码的优化？
image.png
二、堆化
1、什么是批量建堆？
- 就是给定一组数据，基于这组数据直接批量建立一个二叉堆
2、什么是自上而下的上滤？
image.png
3、什么是自下而上的下滤？
image.png
4、自上而下的上滤 VS 自下而上的下滤 性能对比（重点）？
- 自上而下：大部分节点在做工作量比较大的事情
- 自下而上：大部分节点在做工作量比较小的事情
image.png
image.png
5、Top K 的问题解决思路（要能口述）？
image.png
6、二叉堆完整代码，注意 siftUp、siftDown、heapify 三个方法即可
import java.util.Comparator;
/**
* 二叉堆（最大堆）
*
* @param <E>
*/
@SuppressWarnings("unchecked")
public class BinaryHeap<E> extends AbstractHeap<E> {
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public BinaryHeap(E[] elements, Comparator<E> comparator) {
super(comparator);
if (elements == null || elements.length == 0) {
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
} else {
size = elements.length;
int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
this.elements = (E[]) new Object[capacity];
for (int i = 0; i < elements.length; i++) {
this.elements[i] = elements[i];
}
heapify();
}
}
public BinaryHeap(E[] elements) {
this(elements, null);
}
public BinaryHeap(Comparator<E> comparator) {
this(null, comparator);
}
public BinaryHeap() {
this(null, null);
}
@Override
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
@Override
public void add(E element) {
elementNotNullCheck(element);
ensureCapacity(size + 1);
elements[size++] = element;
siftUp(size - 1);
}
@Override
public E get() {
emptyCheck();
return elements[0];
}
@Override
public E remove() {
emptyCheck();
int lastIndex = --size;
E root = elements[0];
elements[0] = elements[lastIndex];
elements[lastIndex] = null;
siftDown(0);
return root;
}
@Override
public E replace(E element) {
elementNotNullCheck(element);
E root = null;
if (size == 0) {
elements[0] = element;
size++;
} else {
root = elements[0];
elements[0] = element;
siftDown(0);
}
return root;
}
/**
* 批量建堆
*/
private void heapify() {
// 自上而下的上滤
// for (int i = 1; i < size; i++) {
// siftUp(i);
// }
// 自下而上的下滤
for (int i = (size >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
}
/**
* 让index位置的元素下滤
* @param index
*/
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1;
// 第一个叶子节点的索引 == 非叶子节点的数量
// index < 第一个叶子节点的索引
// 必须保证index位置是非叶子节点
while (index < half) {
// index的节点有2种情况
// 1.只有左子节点
// 2.同时有左右子节点
// 默认为左子节点跟它进行比较
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
// 右子节点
int rightIndex = childIndex + 1;
// 选出左右子节点最大的那个
if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
child = elements[childIndex = rightIndex];
}
if (compare(element, child) >= 0) break;
// 将子节点存放到index位置
elements[index] = child;
// 重新设置index
index = childIndex;
}
elements[index] = element;
}
/**
* 让index位置的元素上滤
* @param index
*/
private void siftUp(int index) {
// E e = elements[index];
// while (index > 0) {
// int pindex = (index - 1) >> 1;
// E p = elements[pindex];
// if (compare(e, p) <= 0) return;
//
// // 交换index、pindex位置的内容
// E tmp = elements[index];
// elements[index] = elements[pindex];
// elements[pindex] = tmp;
//
// // 重新赋值index
// index = pindex;
// }
E element = elements[index];
while (index > 0) {
int parentIndex = (index - 1) >> 1;
E parent = elements[parentIndex];
if (compare(element, parent) <= 0) break;
// 将父元素存储在index位置
elements[index] = parent;
// 重新赋值index
index = parentIndex;
}
elements[index] = element;
}
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
private void emptyCheck() {
if (size == 0) {
throw new IndexOutOfBoundsException("Heap is empty");
}
}
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
}
