0 课程地址
https://coding.imooc.com/lesson/207.html#mid=13743
1 重点关注
1.1 基于堆的优先队列
见3.1
1.2 泛型使用
见3.1
方法中只要拿定义就好了，不需要extends
1.3 优先队列常用方法
getSize
isEmpty
入队
出队
查看队首元素
1.4 堆和平衡树的各自优势
你说的对，从时间复杂度的角度，平衡树的性能和堆是一样的。但关键是，复杂度只是一个分析算法性能的理论工具，描述的是n趋于无穷大的性能趋势。但其实，都是O(nlogn)，具体实现的性能差距也需要被重视。否则，我们有AVL树就好了，也不需要红黑树了：）
具体上，堆的优势
1）最关键的，平衡树的旋转耗时；
2）其次，堆可以方便地用数组存储。在数组上做事情，也比用指针快。
代价则是，堆不能做快速的查找或者删除任意元素，它是专门针对“更”快速地寻找最大最小元素设计的动态数据结构。平衡树可以用来快速查找和排序
1.5 排序不用动态数据结构
首先，平衡树，或者堆这种数据结构，关键就是动态，跟排序没有可比性。想排序，当然用排序算法就好，
用这类数据结构的关键，就是“动态”。你的数据要不断进出的。
1.6 堆的复杂度分析
比如作为优先队列，虽然堆能够快速看到最大值，但每次取值之后都要重新维护堆结构，时间复杂度还是O(LogN)，
动态数据排序的话，建堆是O(NLogN)，插入和删除都是O(LogN)，排序是O(NLogN)，整体应该是O(NLogN)；平衡树建树如果我没算错的话应该是O(NLogN)，排序时做一次中序遍历只需要O(N)，整体应该还是(建树+排序)O(NLogN)？
所以除了取前topK个元素这种场景之外，在作为优先队列或者排序时，堆和平衡树是不是都具有相同的时间复杂度，只是因为平衡树旋转比较耗性能，或者堆可以用数组存储所以比链表查询的树结构更快这些优势所以选择堆呢？而平衡树的优势则在于查找？
谢谢老师~
2 课程内容
3 Coding
3.1 基于堆的优先队列
- 优先队列接口
package com.company;
/**
* 优先队列接口
* @author weidoudou
* @date 2023/1/11 5:46
**/
public interface Queue <E>{
/**
* 获取大小
* @author weidoudou
* @date 2023/1/11 5:46
* @return int
**/
int getSize();
/**
* 是否为空
* @author weidoudou
* @date 2023/1/11 5:46
* @return boolean
**/
boolean isEmpty();
/**
* 入队操作
* @author weidoudou
* @date 2023/1/11 5:47
* @param e 请添加参数描述
* @return void
**/
void enqueue(E e);
/**
* 出队操作
* @author weidoudou
* @date 2023/1/11 5:48
* @return E
**/
E dequeue();
/**
* 取出堆顶元素
* @author weidoudou
* @date 2023/1/11 5:48
* @param
* @return E
**/
E getFront();
}
- 优先队列实现类
package com.company;
public class PriorityQueue<E extends Comparable<E>> implements Queue<E>{
//完全二叉堆
private MaxHeap<E> maxHeap;
public PriorityQueue(){
maxHeap = new MaxHeap();
}
@Override
public int getSize() {
return maxHeap.size();
}
@Override
public boolean isEmpty() {
return maxHeap.isEmpty();
}
@Override
public void enqueue(E e) {
maxHeap.shiftup(e);
}
@Override
public E dequeue() {
return maxHeap.remove();
}
@Override
public E getFront() {
return maxHeap.findMax();
}
}
- 最大堆
package com.company;
/**
* 最大堆
* @author weidoudou
* @date 2023/1/3 12:35
**/
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap(){
data = new Array<E>();
}
public MaxHeap(int capacity){
data = new Array<E>(capacity);
}
/**
* heapify 将数组转化为堆(将数组可以看作完全二叉堆)
* @author weidoudou
* @date 2023/1/10 7:34
* @param arr 请添加参数描述
* @return null
**/
public MaxHeap(E[] arr){
data = new Array<>(arr);
for(int i = getParent(arr.length-1);i>=0;i--){
siftDown(i);
}
}
/**
* 获取最大堆的元素个数
* @author weidoudou
* @date 2023/1/3 12:40
* @return int
**/
public int size(){
return data.getSize();
}
/**
* 获取最大堆是否为空
* @author weidoudou
* @date 2023/1/3 12:41
* @return boolean
**/
public boolean isEmpty(){
return data.isEmpty();
}
/**
* 最大堆新增元素
* 1 先加入到最大二叉堆实现的 队列中
* 2 把新加入的元素和父元素对比，若大于父元素，则和父元素交换位置，以此为循环
* @author weidoudou
* @date 2023/1/3 12:42
* @param e 请添加参数描述
* @return void
**/
public void shiftup(E e){
//1 先加入到最大二叉堆实现的 队列中
data.addLast(e);
if(data.getSize()==1){
return;
}
//2 把新加入的元素和父元素对比，若大于父元素，则和父元素交换位置，以此为循环
int k = data.getSize()-1;
loop(k,getParent(k));
}
/**
* 递归调用
* @author weidoudou
* @date 2023/1/4 8:09
* @param k 请添加参数描述
* @param j 请添加参数描述
* @return void
**/
private void loop(int k,int j){
//终止条件
//由于j是父节点，索引总是比较小，如果小于等于0，说明已经是根节点
if(j<0||k<=0||k>data.getSize()-1){
return;
}
//最终循环的位置是该元素小于父元素
if(data.get(k).compareTo(data.get(j))<=0){
return;
}
//子元素和父元素交换位置
data.swap(k,j);
//循环
loop(j,(j-1)/2);
}
/**
* 基本方法获取父节点
* @author weidoudou
* @date 2023/1/4 7:54
* @param child 请添加参数描述
* @return int
**/
private int getParent(int child){
if(child==0){
throw new IllegalArgumentException("当前节点为根节点");
}
return (child - 1) / 2;
}
/**
* 基本方法获取左子节点
* @author weidoudou
* @date 2023/1/4 7:56
* @param parent 请添加参数描述
* @return int
**/
private int getLeftChild(int parent){
return 2 * parent + 1;
}
/**
* 基本方法获取右子节点
* @author weidoudou
* @date 2023/1/4 7:56
* @param parent 请添加参数描述
* @return int
**/
private int getRightChild(int parent){
return 2 * parent + 2;
}
/**
* 最大堆元素的下沉（删除堆顶元素）
* @author weidoudou
* @date 2023/1/5 7:59
* @return void
**/
public E remove(){
//1 校验
E temp = findMax();
//2 删除元素（堆顶和堆的最小值进行交换，删除最大值后，递归堆顶的最小元素和左右子节点比较）
//2.1 特殊化处理，如果只有一个元素
int size = data.getSize();
/* if(size==1){
return data.removFirst();
}*/
//2.2 多个元素
//2.2.1 首尾交换
data.swap(0,size-1);
//2.2.2 删除堆的最大元素
data.removLast();
//2.2.3 递归调用比较堆顶和左右子节点
siftDown(0);
return temp;
}
/**
* 递归调用比较堆顶和左右子节点
* @author weidoudou
* @date 2023/1/5 8:15
* @param i 请添加参数描述
* @return void
**/
private void siftDown(int i){
int j = getLeftChild(i);//左子节点索引
int k = getRightChild(i);//右子节点索引
//1 终止条件
//1.1 无左子节点
if(j>data.getSize()-1){
return;
}
//1.2 左子节点一定有,若左子节点大于根节点，则比较右子节点和左子节点，否则，比较右子节点和根节点
if(data.get(j).compareTo(data.get(i))>0){//无右子节点或者左子节点比右子节点要大，则交换左子节点和父节点
if(k>data.getSize()-1||data.get(j).compareTo(data.get(k))>0){
data.swap(i,j);
siftDown(j);
}else{//左右节点都有并且右子节点大于左子节点
data.swap(i,k);
siftDown(k);
}
}else{//右节点存在并且父节点小于右节点，更换位置，否则不更换
if(k<=data.getSize()-1&&data.get(i).compareTo(data.get(k))<0){
data.swap(i,k);
siftDown(k);
}
}
}
/**
* 取出堆顶元素
* @author weidoudou
* @date 2023/1/10 7:10
* @param
* @return E
**/
public E findMax(){
if(isEmpty()){
throw new IllegalArgumentException("堆为空");
}
return data.get(0);
}
/**
* 替换元素：把堆顶最大的元素取出返回，堆顶放入传过来的元素，然后进行下沉。O(logN)
* 这样比先删，在加2O(logN)复杂度小了一倍
* @author weidoudou
* @date 2023/1/10 7:07
* @param e 请添加参数描述
* @return E
**/
public E replace(E e){
E temp = findMax();
data.set(0,e);
siftDown(0);
return temp;
}
}
- Array类
package com.company;
import java.util.Arrays;
public class Array<E> {
private int size;
//int类型的数组
private E[] data;
//1.1 创建构造函数，传入容量，则新生成一个数组
public Array(int capacity){
data = (E[]) new Object[capacity];
size = 0;
}
//1.2 创建无参构造函数
public Array(){
this(10);
}
//1.3 添加传入静态数组的构造函数
/* public Array(E[] param){
this.data = param;
long outParm = Arrays.stream(param).filter(e->{
return e!=null;
}).count();
this.size = (int)outParm;
}*/
public Array(E[] arr){
data = (E[]) new Object[arr.length];
for(int i = 0;i<arr.length;i++){
data[i] = arr[i];
}
size = arr.length;
}
//2.1 添加getSize,获取数组元素个数
public int getSize(){
return size;
}
//2.2 添加getCapacity,获取数组容量
public int getCapacity(){
return data.length;
}
//2.3 添加数组是否为空方法
public boolean isEmpty(){
return size==0;
}
//3.1 在数组末尾添加元素
public void addLast(E e){
addElement(size,e);
}
//3.2 在数组起始添加元素
public void addFirst(E e){
addElement(0,e);
}
//3.3 数组根据索引添加元素
public void addElement(int index,E e){
//1 校验异常
//1.1 如果数组已经满了，则禁止插入
if(size== data.length){
//todo 并不会，需要把值一条一条的赋进来
resize(2*size);
//throw new IllegalArgumentException("数组已满，禁止插入");
}
//1.2 如果传入的索引在已有数组的索引之外，则校验异常
if(index<0||index>size){
throw new IllegalArgumentException("索引应在已有数组的索引之间");
}
//2 实现根据索引添加元素的逻辑
//2.1 data同步
for(int j = size-1;j>=index;j--){
data[j+1] = data[j];
}
data[index] = e;
//2.2 size同步
size++;
}
//6.1 数组动态伸缩 这里用size更好，想想为什么
private void resize(int capacity){
E[] newData = (E[]) new Object[capacity];
for(int i = 0;i < size;i++){
newData[i] = data[i];
}
data = newData;
}
//4.1 数组 toString 范例
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append(String.format("Array:size = %d,capacity = %d\n",size,data.length));
stringBuffer.append("[");
for(int i=0;i<size;i++){
stringBuffer.append(data[i]);
if(i!=size-1){
stringBuffer.append(",");
}
}
stringBuffer.append("]");
return stringBuffer.toString();
}
//4.2 get获取元素
public E get(int index){
if(index<0||index>data.length){
throw new IllegalArgumentException("111");
}
return data[index];
}
//4.3 set获取元素
public void set(int index,E e){
if(index<0||index>data.length){
throw new IllegalArgumentException("111");
}
data[index] = e;
}
//5.1 数组包含
public boolean contails(E e){
for(int i = 0;i<size;i++){
if(e.equals(data[i])){
return true;
}
}
return false;
}
//5.2 数组搜索
public int search(E e){
for(int i = 0;i<size;i++){
if(e.equals(data[i])){
return i;
}
}
return -1;
}
//5.3 数组删除，通常情况下做删除，会在出参把删除的值带出来
public E remove(int index){
if(index<0||index>=size){
throw new IllegalArgumentException("111");
}
E outParm = data[index];
for(int i=index;i<size-1;i++){
data[i] = data[i+1];
}
//这块不塞值也没有任何影响，因为size已经--了，不会访问到size之外的元素
data[size-1]= null;
size--;
if(size == data.length/2){
resize(data.length/2);
}
return outParm;
}
//5.4 删除首个元素
public E removFirst(){
return remove(0);
}
//5.5 删除最后的元素
public E removLast(){
return remove(size-1);
}
//5.6 删除指定的元素
public void removElement(E e){
int index = -1;
//判断删除的元素是否存在
for(int i=0;i<size;i++){
if(e.equals(data[i])){
index = i;
break;
}
}
if(index>=0){
remove(index);
}else{
throw new IllegalArgumentException("删除的元素未找到");
}
}
/**
* 交换元素位置
* @author weidoudou
* @date 2023/1/4 8:19
* @param k 请添加参数描述
* @param j 请添加参数描述
* @return void
**/
public void swap(int k,int j){
if(k<0||j<0||k>=size||j>=size){
throw new IllegalArgumentException("索引不正确");
}
E temp = data[k];
data[k] = data[j];
data[j] = temp;
}
}
标签：return,队列,节点,int,玩转,数据结构,data,public,size From： https://www.cnblogs.com/1446358788-qq/p/17042722.html