1. 思考
-
Top k 问题： 从海量数据中获取前k个 最大值 或 最小值；
比如从 一百万 个整数中，获取最大的1000个整数； -
设计一种数据结构，用来存放整数元素，包括的操作是 获取最大值，添加元素，删除最大值：
各数据结构的时间复杂度对比
-
为了能达到最优，使用 堆：
堆：获取最大值时间复杂度O(1)，添加元素时间复杂度O(log n)，删除最大值时间复杂度O(log n)；
2. 堆 (Heap)
- 这里的 堆 是一种数据结构，不是指内存中堆，堆一般分为：
- 二叉堆（Binary Heap，完全二叉堆）；
- 多叉堆（D-heap、D-ary Heap）;
- 索引堆（Index Heap）;
- 二项堆（Binomial Heap）；
- 斐波那契堆（Fibonacci Heap）；
- 左倾堆（Leftist Heap）；
- 斜堆（Skew Heap）；
- 堆的最重要性质：任意节点的值总是
或者
子节点的值：
- 如果任意节点的值
- 如果任意节点的值
3. 二叉堆 (Binary Heap)
二叉堆 的数据结构是一棵完全二叉树，因此也被称为完全二叉堆;
鉴于二叉堆的结构，底层可以用 数组 实现；
最大二叉堆数据结构
- 二叉堆的 索引 规律（从0开始，与数组对应）
- i = 0 , 表示根节点；
- i > 0 ，则父节点索引为floor( (i-1) / 2)；
- 如果 2i + 1 <= n - 1， 它的左子树索引为 2i + 1 ；
- 如果 2*i + 1 > n - 1 ，该节点无左子树；
- 如果 2i + 2 <= n -1 ,该节点的右子节点索引为 2i + 2;
- 如果 2*i + 2 > n - 1，该节点无右子节点；
- 二叉堆的接口设计
- int size();
//返回二叉堆元素个数；
- boolean isEmpty();
- void clear();
- void add(E element);
- E get();
- E remove();
- E replace(E element);
4. 二叉堆 获取最大值
获取堆顶，就能获取最大值
public E get() {
emptyCheck();
return elements[0];
}
5. 二叉堆 添加元素
二叉堆添加元素（添加85）
- 如果node的值 > 父节点的值；
- 与父节点交互位置
- 如果node的值 <= 父节点的值，或者node没有父节点；
- 退出循环
- 这个过程叫做上滤(Sift Up)；
- 时间复杂度为 O( log n)
// 添加元素
public void add(E element) {
elementNotNullCheck(element);
ensureCapacity(size + 1);
elements[size++] = element;
siftUp(size - 1);
}
// 上滤
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;
}
}
6. 二叉堆 删除最大值
二叉堆 删除元素（删除85）
堆是一种数据结构，只能删除 堆顶 元素，所以删除 最大值，不能删除其他位置的，参考栈结构。删除的操作如下：
- 将存放堆的数组最后一个元素，覆盖堆顶（node），然后将数组最后一个元素删除；
- 如果该节点（node）的值 < 最大子节点的值；
- 将node与子节点交互位置；
- 如果该节点（node）的值 >= 最大子节点的值，或者已经没有子节点了；
- 退出循环；
- 该过程称为下滤（Shit Down）;
- 时间复杂度为 O( log n)
// 删除堆顶
public E remove() {
emptyCheck();
int lastIndex = --size;
E root = elements[0];
elements[0] = elements[lastIndex];
elements[lastIndex] = null;
siftDown(0);
return root;
}
// 下滤
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1;
// half 为第一个叶子节点索引
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;
}
6. 二叉堆 替换堆顶元素
替换（replace）和删除最大值一样，都是替换堆顶元素，然后判断是否大于 最大子节点，如果大于，那么进行 下滤，直到小于或者是叶子节点才退出循环；
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;
}
7. 小顶堆的创建
以上所讲的都是大顶堆，小顶堆的创建非常简单，只要修改compare的函数就可以。
小顶堆
// 大顶堆的compare
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
// 小顶堆的compare
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
8. 应用
1. Top k 问题
- 从n个整数/浮点数中，取出k个最大值，其中 k 远远小于 n；
- 可以使用全排序进行来得出最大的k个值，但是时间复杂度为O( n log n);
- 使用二叉堆，时间复杂度为 O( n log k);
步骤如下：
- 创建一个小顶堆；
- 遍历这n个值；
- 先将 k 个值，添加到小顶堆中；
- 从第k+1个值开始，先获取堆顶元素（ heap.get() ），比较；
- 如果大于堆顶元素，替换堆顶，进行下滤操作；
- 如果小于等于堆顶元素，循环下一个元素；
- 遍历结束后，存放k个值的小顶堆，就是存放最大的k个值；
for (int i = 0; i < data.length; i++) {
if (heap.size() < k) { // 前k个数添加到小顶堆
heap.add(data[i]);
} else if (data[i] > heap.get()) { // 如果是第k + 1个数，并且大于堆顶元素
heap.replace(data[i]);
}
}
2. 优先级队列
- 创建一个大顶推；
- 设置队列节点的优先级权重；
- 以权重来实现作为compare的判断条件；
- 这样权重最大的节点，被放在堆顶，权重越小的就放在后面的节点；
- 在执行队列时，会调用remove()，获取堆顶的节点，执行操作；
网友评论