0 课程地址
https://coding.imooc.com/lesson/207.html#mid=13740
1 重点关注
1.1 二叉堆插值
见3.1
2 课程内容
3 Coding
3.1 向最大二叉堆添加元素
- 关键代码
/**
* 最大堆新增元素
* 1 先加入到最大二叉堆实现的 队列中
* 2 把新加入的元素和父元素对比，若大于父元素，则和父元素交换位置，以此为循环
* @author weidoudou
* @date 2023/1/3 12:42
* @param e 请添加参数描述
* @return void
**/
public void shiftup(E e){
//1 先加入到最大二叉堆实现的 队列中
data.addLast(e);
//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){
return;
}
//最终循环的位置是该元素小于父元素
if(data.get(k).compareTo(data.get(j))<=0){
return;
}
//子元素和父元素交换位置
data.swap(k,j);
//循环
loop(j,(j-1)/2);
}
- 全量代码
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);
}
/**
* 获取最大堆的元素个数
* @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);
//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){
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;
}
}
- 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;
}
//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;
}
}
标签：int,void,元素,Up,Sift,数据结构,data,public,size From： https://www.cnblogs.com/1446358788-qq/p/17023894.html