堆
堆本身也是一棵树，二叉堆也是二叉树，只不过满足一些特殊的性质二叉树，与树一样可以有多叉堆
最大（小）堆
- 是一颗完全二叉树，节点依次的排列节点，就可以采用线性结构存储各个节点，很容易找到规律
- 堆顶元素若是1时，从数组中的第1号元素开始存储，此时更好找规律，但是会浪费一个存储空间，若当前节点是
i那么他的父节点是i/2（整型除法），左子节点是i*2，右子节点是i*2+1 - 堆顶元素若是0时，从数组中的第0号元素开始存储，将刚才的规律向右偏移，若当前节点是
i那么他的父节点是(i-1)/2（整型除法），左子节点是i*2+1，右子节点是i*2+2
- 堆顶元素若是1时，从数组中的第1号元素开始存储，此时更好找规律，但是会浪费一个存储空间，若当前节点是
50,1 | 50,0
/ \ | / \
40,2 10,3 | 40,1 10,2
/ \ | / \
30,4 20,5 | 30,3 20,4
- 堆中任意节点的值，总是不大于其父亲节点的值（即堆顶是最大元素节点，任何子堆的堆顶也满足此定义），但是不要错误的认为层次比较低的节点一定小于层次比较高的的节点，比如同一层两个节点分别是10和100，他们的子节点会在第下一层，但是100的子节点可能大于10，因为子节点只是不大于父节点，并没有说不大于父亲的兄弟节点
/**
* @ClassName: Heap
* @Description: 基于动态数组实现的自定义堆
*/
public class Heap<E extends Comparable> { //使用堆存储必须实现比较器接口
private Array<E> array;
/**
* @MethodName: Heap
* @Param capacity: 用户指定的容量
* @Description: 根据用户需求创建指定大小容量的堆
*/
public Heap(int capacity) {
this.array = new Array<>(capacity);
}
/**
* @MethodName: Heap
* @Description: 为用户设置默认的容量大小，为10
*/
public Heap() {
this.array = new Array<>(10);
}
/**
* @MethodName: Heap
* @Description: 将数组转化为堆的数据结构
* @Param arr: 用户传来的数组
*/
public Heap(E[] arr) {
//此时传入的只能是包装类对象数组
/**
* 分析：
* 虽然可以使用add()方法可以将数组中的每个元素都添加到堆中，但是由于堆是基于
* 数组的，大可不必将每个元素都添加到堆中，而是将数组中元素位置稍作修改就可
* 改变为堆，而且在数组基础上修改还可以大大减少遍历数组的次数，因为堆的叶子
* 节点可以无需下沉到合法位置，非叶子节点的下沉就可以将叶子节点推向合法位置
*
* 由于堆是一层一层从左到右依次顺序存储的，所以最后一个非叶子节点就是堆低节
* 点的父节点，从该节点开始不断栈顶遍历执行下沉操作即可
*/
this.array = new Array<>(arr.length + 10);
//开辟一个比传入数组稍微大点的动态数组
for (int i = 0; i < arr.length; i++) {
//将传入数组添加到动态数组中
this.array.addLast(arr[i]);
}
for (int i = parent(this.array.getSize() - 1); i >= 0; i--) {
//从最后一个非叶子节点开始向堆顶遍历
this.siftDown(i); //让该节点执行下沉操作
}
}
/**
* @MethodName: parent
* @Description: 获取当前节点父节点的索引
* @Param index: 当前节点索引
* @Return int
*/
private int parent(int index) {
return (index - 1) / 2;
}
/**
* @MethodName: leftChild
* @Description: 获取当前节点左子节点的索引
* @Param index: 当前节点索引
* @Return int
*/
private int leftChild(int index) {
return index * 2 + 1;
}
/**
* @MethodName: rightChild
* @Description: 获取当前节点右子节点的索引
* @Param index: 当前节点索引
* @Return int
*/
private int rightChild(int index) {
return index * 2 + 2;
}
/**
* @MethodName: swap
* @Description: 交换数组中两个元素位置
* @Param x: 第一个元素
* @Param y: 第二个元素
* @Return void
*/
private void swap(int x, int y) {
E temp = this.array.get(x); //t=x
this.array.set(x, this.array.get(y)); //x=y
this.array.set(y, temp); //y=t
}
/**
* @MethodName: add
* @Description: 向堆中添加指定元素
* @Param element: 指定的元素
* @Return void
*/
public void add(E element) {
/**
* 分析：
* 向堆中添加元素，必然是向堆底部添加该元素，添加的元素很有可能不满足
* 该节点不大于其父节点的性质，就需要将该节点与父节点作比较，若不满足
* 就与父节点交换位置（即上浮），这应该是一个递归的过程，但是由于使用
* 的是线性结构存储的堆，所以可以采用循环判断更加容易一些
*/
this.array.addLast(element); //添加到堆的底部
this.siftUp(this.array.getSize() - 1); //将添加的节点上浮到合法位置
}
/**
* @MethodName: siftUp
* @Description: 将当前元素上浮到合法位置
* @Param index: 当前元素索引
* @Return void
*/
private void siftUp(int index) {
while (index > 0 &&
this.array.get(index).compareTo(this.array.get(this.parent(index))) > 0) {
//若当前节点索引未到数组头部，并且当前节点大于父节点
this.swap(index, this.parent(index)); //交互子节点和父节点位置
index = this.parent(index); //交换后，当前节点就成了父节点
}
}
/**
* @MethodName: roof
* @Description: 查看堆顶元素
* @Return E
*/
public E peek() {
if (this.isEmpty()) { //若堆中没有元素，会抛出异常
throw new IllegalArgumentException("Get failed, Heap is empty");
}
return this.array.get(0); //获取堆顶元素
}
/**
* @MethodName: remove
* @Description: 从堆顶删除元素，并返回删除元素
* @Return E
*/
public E remove() {
/**
* 分析：
* 从堆中删除元素，必然是从堆顶删除元素，此时就会成为两个堆，融合起来
* 是比较复杂的，但是若使用堆低元素暂时替代被删除的堆顶元素，该堆的形
* 态就不会被破坏，此时该替换的堆低元素一定不满足父节点大于其所有孩子
* 节点的性质，这就需要将该节点与两个孩子节点做比较，与两个孩子节点中
* 较大的那个节点进行交换位置（即下沉），这一个是一个递归的过程，但是
* 由于使用的是线性结构存储的堆，所以可以采用循环判断更加容易一些
*/
if (this.isEmpty()) { //若堆中没有元素，不能删除，会抛出异常
throw new IllegalArgumentException("Get failed, Heap is empty");
}
this.swap(0, this.array.getSize() - 1); //将堆顶元素与堆底节点交换位置
E ret = this.array.removeLast(); //将刚才交换前的堆顶节点删除，并暂存
this.siftDown(0); //将交换后的堆顶节点下沉到合法位置
return ret; //返回删除的堆顶元素
}
/**
* @MethodName: siftDown
* @Description: 将当前元素下沉到合法位置
* @Param index: 当前元素索引
* @Return void
*/
private void siftDown(int index) {
while (this.leftChild(index) < this.array.getSize()) {
//由于堆是一层一层从左到右依次顺序存储的，所以没有左孩子就一定没有右孩子
//当一个节点没有左孩子时（左孩子索引越界），已经到最后一层了，就没有孩子可比较了
int maxIndex = this.leftChild(index); //若只有左孩子只需要与左孩子做比较看是否交换
if (this.rightChild(index) < this.array.getSize()) {
//若存在右孩子（右孩子索引越界），就要比较左右孩子谁更大，与更大的交换
int leftChildIndex = this.leftChild(index);
int rightChildIndex = this.rightChild(index);
maxIndex = this.array.get(leftChildIndex).
compareTo(this.array.get(rightChildIndex)) > 0 ? leftChildIndex : rightChildIndex;
}
if (this.array.get(index).compareTo(this.array.get(maxIndex)) < 0) {
//若当前节点与小于较大的孩子节点时需要交换位置
this.swap(index, maxIndex);
index = maxIndex; //交换后当前节点就成了较大的孩子节点
} else { //若当前节点已经大于了较大的孩子节点时，已满足定义
break; //跳出循环
}
}
}
/**
* @MethodName: replace
* @Description: 将堆顶元素取出同时添加一个元素
* @Param element:
* @Return E
*/
public E replace(E element) {
/**
* 分析：
* 虽然可以先使用remove()方法再使用add()方法完成该操作，但是删除时是将
* 堆顶和堆低元素交换后再下沉，再加上添加元素的上浮操作，共做了两次让元
* 素位置合法的操作，若将删除操作改一改，将堆顶元素直接替换为要添加的操
* 作就可以只需要一次下沉就可以让元素位置合法
*/
if (this.isEmpty()) { //若堆中没有元素，不能删除，会抛出异常
throw new IllegalArgumentException("Get failed, Heap is empty");
}
E ret = this.array.get(0); //将将堆顶元素暂存
this.array.set(0, element);//将堆顶元素替换
this.siftDown(0); //将替换后的堆顶节点下沉到合法位置
return ret; //返回删除的堆顶元素
}
/**
* @MethodName: getSize
* @Description: 获取堆中元素个数
* @Return int
*/
public int getSize() {
return this.array.getSize();
}
/**
* @MethodName: isEmpty
* @Description: 判断堆是否为空
* @Return boolean
*/
public boolean isEmpty() {
return this.array.isEmpty();
}
}
Comments NOTHING