个人学习笔记--数据结构与算法-二叉堆与优先级队列（十一）
程序员文章站
2022-03-12 17:10:16
...
以下是学习恋上数据结构与算法的学习笔记，本篇主要内容是二叉堆与优先级队列
◼设计一种数据结构，用来存放整数，要求提供3 个接口
●添加元素●获取最大值●删除最大值
◼有没有更优的数据结构？
●堆✓获取最大值：O(1)、删除最大值：O(logn)、添加元素：O(logn)
◼堆（Heap）
也是一种树状的数据结构（不要跟内存模型中的“堆空间”混淆），常见的堆实现有：✓二叉堆（Binary Heap，完全二叉堆）✓多叉堆（D-heap、D-ary Heap）✓索引堆（Index Heap）✓二项堆（BinomialHeap）✓斐波那契堆（Fibonacci Heap）✓左倾堆（Leftist Heap，左式堆）✓斜堆（Skew Heap）
◼堆的一个重要性质：任意节点的值总是≥（≤）子节点的值
●如果任意节点的值总是≥子节点的值，称为：最大堆、大根堆、大顶堆
●如果任意节点的值总是≤子节点的值，称为：最小堆、小根堆、小顶堆
◼由此可见，堆中的元素必须具备可比较性
二叉堆（Binary Heap）
●二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆
●鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用数组实现即可
◼索引i 的规律（n 是元素数量）
✓如果i = 0 ，它是根节点
✓如果i > 0 ，它的父节点的索引为floor( (i –1) / 2 )
✓如果2i + 1 ≤ n –1，它的左子节点的索引为2i + 1
✓如果2i + 1 > n –1 ，它无左子节点
✓如果2i + 2 ≤ n –1 ，它的右子节点的索引为2i + 2
✓如果2i + 2 > n –1 ，它无右子节点
◼获取最大值
堆是返回得到堆顶元素
所以如果是大顶堆则是数组第一个元素
◼最大堆–添加
/**
* 让index位置的元素上滤
* @param index
*/
private void siftUp(int index) {
E element = elements[index];//得到该index位置的元素
while(index>0) {
int parentIndex = (index-1)>>1;//父节点的索引为floor( (i –1) / 2 )
E parent = elements[parentIndex];
if(compare(element, parent)<=0) break;
//将父元素存储在index位置
elements[index] = parent;
//重新赋值index
index = parentIndex;
}
elements[index] = element;//将循环最后得到的index位置 放上element值，完成上滤
}
◼最大堆–删除
/**
* 让index位置的元素下滤
* @param index
*/
private void siftDown(int index) {
E element = elements[index];
int half = size>>1;
//第一个叶子节点的索引 == 非叶子节点的数量
//index 《 第一个叶子节点的索引 因为叶子节点不用下滤了
//所以必须保证index位置是非叶子节点
while(index<half) {
//index的节点只有两种情况，1.只有左节点 2.同时有左右节点
//默认是左节点进行比较
int childIndex = (index<<1)+1;//它的左子节点的索引为2i + 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;
}
◼最大堆–批量建堆（Heapify）
◼批量建堆，有2 种做法
●自上而下的上滤
●自下而上的下滤
◼Top K问题
◼从n 个整数中，找出最大的前k 个数（k 远远小于n ）
◼如果使用排序算法进行全排序，需要O(nlogn) 的时间复杂度
◼如果使用二叉堆来解决，可以使用O(nlogk) 的时间复杂度来解决
●新建一个小顶堆
●扫描n 个整数
✓先将遍历到的前k 个数放入堆中
✓从第k + 1 个数开始，如果大于堆顶元素，就使用replace 操作（删除堆顶元素，将第k + 1 个数添加到堆中）
●扫描完毕后，堆中剩下的就是最大的前k 个数
// 新建一个小顶堆
BinaryHeap<Integer> heap = new BinaryHeap<>(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]); // logk
} else if (data[i] > heap.get()) { // 如果是第k + 1个数，并且大于堆顶元素
heap.replace(data[i]); // logk
}
}
◼如果是找出最小的前k 个数呢？
●用大顶堆
●如果小于堆顶元素，就使用replace 操作
◼优先级队列（Priority Queue）
◼优先级队列也是个队列
◼普通的队列是FIFO 原则，也就是先进先出
◼优先级队列则是按照优先级高低进行出队，比如将优先级最高的元素作为队头优先出队
◼优先级队列的详细设计代码，二叉堆实现
public class PriorityQueue<E> {
private BinaryHeap<E> heap;//二叉堆
public PriorityQueue(Comparator<E> comparator) {
heap = new BinaryHeap<>(comparator);
}
public PriorityQueue() {
this(null);
}
public int size() {
return heap.size();
}
public boolean isEmpty() {
return heap.isEmpty();
}
public void clear() {
heap.clear();
}
public void enQueue(E element) {
heap.add(element);
}
public E deQueue() {
return heap.remove();
}
public E front() {
return heap.get();
}
}
◼二叉堆的详细设计代码
package com.bj.heap;
import java.util.Comparator;
public class BinaryHeap2<E> {
private E[] elements;//数组
private static final int DEFAULT_CAPACITY=10;//默认大小
protected int size;
protected Comparator<E> comparator;
public BinaryHeap2(E[] elements, Comparator<E> 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 BinaryHeap2(E[] elements) {
this(elements, null);
}
public BinaryHeap2(Comparator<E> comparator) {
this(null, comparator);
}
public BinaryHeap2() {
this(null, null);
}
public int size() {
return size;
}
public boolean isEmpty() {
return size==0;
}
//清空
public void clear() {
for(int i = 0;i<size;i++) {
elements[i] = null;
}
size=0;
}
public void add(E element) {
elementNotNullCheck(element);
ensureCapacity(size + 1);
elements[size++] = element;//先往数组最后添加元素
siftUp(size-1);//再进行上滤
}
//堆是返回得到堆顶元素
public E get() {
emptyCheck();
return elements[0];
}
public E remove() {
emptyCheck();
int lastIndex = --size;
E root = elements[0];
elements[0] = elements[lastIndex];
elements[lastIndex] = null;
siftDown(0);
return root;
}
// 删除堆顶元素的同时插入一个新元素
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的节点只有两种情况，1.只有左节点 2.同时有左右节点
//默认是左节点进行比较
int childIndex = (index<<1)+1;//它的左子节点的索引为2i + 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 element = elements[index];//得到该index位置的元素
while(index>0) {
int parentIndex = (index-1)>>1;//父节点的索引为floor( (i –1) / 2 )
E parent = elements[parentIndex];
if(compare(element, parent)<=0) break;
//将父元素存储在index位置
elements[index] = parent;
//重新赋值index
index = parentIndex;
}
elements[index] = element;//将循环最后得到的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");
}
}
private int compare(E e1, E e2) {
return comparator != null ? comparator.compare(e1, e2)
: ((Comparable<E>)e1).compareTo(e2);
}
}
推荐阅读
-
数据结构与算法——优先队列类的C++实现(二叉堆)
-
个人学习笔记--数据结构与算法--二叉树（四）
-
个人学习笔记--数据结构与算法--二叉搜索树（五）
-
数据结构与算法分析-C++描述 第6章 优先队列ADT（二叉堆）
-
[数据结构与算法] 优先级队列/堆队列 完全二叉堆 左式堆 python里的heapq
-
小鱼要学数据结构与算法（基于python)—Day19树的遍历、优先队列和二叉堆
-
数据结构与算法（六）二叉堆、优先队列和Java PriorityQueue
-
数据结构与算法——优先队列类的C++实现(二叉堆)
-
【数据结构与算法python】完全二叉树的实现（优先队列和二叉堆）
-
个人学习笔记--数据结构与算法-二叉堆与优先级队列（十一）