16_二叉堆
2020-09-10 本文已影响0人
伶俐ll
思考：设计一种数据结构，用来存放整数，要求提供三个接口：添加元素/删除最大值/获取最大值
Snip20200909_3.png
那么有没有更优的数据结构？可以使用堆来实现
- 添加元素：O(logn)
- 获取最大值：O(1)
- 删除最大值：O(logn)
堆（Heap）
堆也是一种树状的数据结构，常见的堆实现有
- 二叉堆（Binary Heap，完全二叉堆）
- 多叉堆（D-heap、D-ary Heap）
- 索引堆（Index Heap）
- 二项堆（Binomial Heap）
- 斐波那契堆（Fibonacci Heap）
- 左倾堆（Leftist Heap，左式堆）
- 斜堆（Skew Heap）
堆的特性：
任意节点的值总是>= ( <=) 子节点的值，因此，堆中的元素必须具备可比较性（跟二叉搜索树一样）
- 如果任意节点的值总是>=子节点的值，称为：最大堆、大根堆、大顶堆
- 如果任意节点的值总是 <= 子节点的值，称为：最小堆、小根堆、小顶堆
Snip20200910_7.png
堆的接口设计
int size(); // 元素的数量boolean isEmpty(); // 是否为空void clear(); // 清空void add(E element); // 添加元素E get(); // 获得堆顶元素E remove(); // 删除堆顶元素E replace(E element); // 删除堆顶元素的同时插入一个新元素
二叉堆（Binary Heap）
- 二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆
- 鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用数组实现即可
批量建堆（Heapify）
批量建堆有两种做法：
-
自上而下的上滤
Snip20200910_2.png
for(int i = 1;i<size;i++){
siftUp(i);
}
-
自下而上的下滤
Snip20200910_3.png
for (int i = (size >> 1) - 1;i>=0;i--){
siftDown(i);
}
-
效率对比
Snip20200910_4.png
- 深度之和：仅仅是叶子节点，就有近 n/2 个，而且每个叶子节点的深度都是 O(logn)级别，因此，在叶子节点这一块，就达到了O(nlogn)级别；
- 高度之和：O(n)
二叉堆代码实现
/**
* 二叉堆
*/
package Heap;
import java.util.Comparator;
public class LZBinaryHeap <E> {
private int size;
private E[] elements;
private Comparator<E> comparator;
private static final int DEFAULT_CAPACITY = 10;
/**
* 构造函数：批量建堆
* @param elements
* @param comparator
*/
public LZBinaryHeap(E[] elements,Comparator comparator){
this.comparator = comparator;
if (elements == null || elements.length == 0){
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
}else {
int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
this.elements = (E[]) new Object[capacity];
this.size = elements.length;
for (int i = 0;i< elements.length;i++){
this.elements[i] = elements[i];
}
heapify();
}
}
/**
* 构造函数
*/
public LZBinaryHeap(Comparator comparator){
this(null,comparator);
}
/**
* 构造函数
*/
public LZBinaryHeap(){
this(null);
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 清空
*/
public void clear(){
for (int i = 0;i<size;i++){
elements[i] = null;
}
size = 0;
}
/**
* 添加元素
* @param element
*/
public void add(E element){
/**
* 1. 判断是否需要扩容，如果需要扩容首先扩容
* 2. 将元素添加到数组的最后一个位置，size++
* 3. 上滤，将元素向上移动到正确的位置
*/
//扩容
ensureCapacity();
// 添加元素到数组size位置，成为数组最后一个元素
elements[size++] = element;
// 上滤
siftUp(size-1);
}
/**
* 获取堆顶元素
* @return
*/
public E get(){
//非空检查
emptyCheck();
return elements[0];
}
/**
* 删除堆顶元素
* @return
*/
public E remove(){
/**
* 1. 用最后一个节点覆盖根节点
* 2. 删除最后一个节点，size--
* 3. 根节点下滤
*/
//非空检查
emptyCheck();
//获取堆顶元素
E first = elements[0];
//获取数组中最后一个元素，并将数组的长度减1
int lastIndex = --size;
//将最后一个元素放到堆顶位置
elements[0] = elements[lastIndex];
//将数组最后一个位置清空
elements[lastIndex] = null;
//下滤，将堆顶元素下沉到合适位置
siftDown(0);
return first;
}
/**
* 删除堆顶元素的同时插入一个新的元素
* @param element
* @return
*/
public E replace(E element){
/**
* 1. 如果插入的是第一个元素，则之间添加，返回null
* 2. 如果数组中已经有元素，则将堆顶元素返回，
* 用新添加元素覆盖堆顶元素，将堆顶元素下滤
*/
emptyCheck();
E top = null;
if (size == 0){
elements[size++] = element;
}else {
top = elements[0];
elements[0] = element;
siftDown(0);
}
return top;
}
/**
* 上滤——将元素向上移动到正确的位置
* 时间复杂度O(logn)
* 1. 如果节点大于其父节点，与父节点交换位置
* 2. 如果节点于等于其父节点，或者没有父节点，那么节点则移动到了正确的位置，
* 退出循环
*/
private void siftUp(int index){
E element = elements[index];
while (index>0){
int parentIndex = (index - 1) >>1;
E parent = elements[parentIndex];
if (compare(parent,element) >= 0) break;
elements[index] = parent;
index = parentIndex;
}
elements[index] = element;
}
/**
* 下滤 -- 将元素向下移动到正确的位置
* 时间复杂度 O(logn)
* 1. 如果节点小于最大子节点，与最大的子节点交换位置
* 2. 如果节点大于等于最大子节点，或者没有子节点，那么节点则移动到了正确的位置
* 退出循环
* @param index
*/
private void siftDown(int index){
E element = elements[index];
//half : 非叶子节点数量，也就是第一个叶子节点的下标
int half = (size >> 1);
while (index<half){
//index >= half 说明index位置节点是叶子节点，节点已经移动到了正确的位置，退出循环
// 左子节点
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
// 右子节点
int rightIndex = childIndex + 1;
//选出左右子节点最大的那个
if (rightIndex<size && (compare(child,elements[rightIndex]) < 0)){
childIndex = rightIndex;
child = elements[rightIndex];
}
if (compare(element,child) >= 0) break;
elements[index] = child;
index = childIndex;
}
elements[index] = element;
}
/**
* 批量建堆
*/
private void heapify(){
// for(int i = 1;i<size;i++){
// siftUp(i);
// }
for (int i = (size >> 1) - 1;i>=0;i--){
siftDown(i);
}
}
/**
* 扩容
*/
private void ensureCapacity(){
int oldCapacity = elements.length;
if (elements.length >= size + 1) return;
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 int compare(E e1,E e2){
if (comparator != null) return comparator.compare(e1,e2);
return ((Comparable<E>)e1).compareTo(e2);
}
}
小顶堆
//小顶堆
LZBinaryHeap<Integer> heap = new LZBinaryHeap<>(new Comparator<Integer>(){
public int compare(Integer o1,Integer o2){
return o2 - o1;
}
});
Top K问题
从海量数据中找出前k个数据
例如：从n个整数中找出最大的k个整数（k远远小于n）
-
使用排序算法进行全排序，需要O(nlogn)的时间复杂度
-
使用二叉堆来解决，仅需要O(nlogk)的时间复杂度
步骤：
1. 新建一个小顶堆
2. 扫描n个整数，将遍历的前k个数放入堆中
3. 从第k+1个数开始，如果大于堆顶元素，就使用replace操作（删除堆顶元素，将第k+1个数添加到堆中）
4. 扫描完毕后，堆中剩下的就是最大的前k个数 -
如果是找出最小的前k个数呢
利用大顶堆，如果小于堆顶元素，就使用replace操作
代码实现
//新建一个小顶堆
LZBinaryHeap<Integer> heap = new LZBinaryHeap<>(new Comparator<Integer>(){
public int compare(Integer o1,Integer o2){
return o2 - o1;
}
});
//找出最大的前k个数
int k = 3;
Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93,
91, 19, 54, 47, 73, 62, 76, 63, 35, 18,
90, 6, 65, 49, 3, 26, 61, 21, 48};
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上的元素永远是最大的k个
heap.replace(data[i]);
}
}
