共计 3029 个字符,预计需要花费 8 分钟才能阅读完成。
二叉堆
二叉堆是一颗二叉树,不一定是满二叉树,但一定是完全二叉树,完全二叉树指的是允许有缺失的部分,但缺失节点的部分一定是右下侧。
堆中任意一个节点的值一定大于等于他的孩子节点。这个特点也说明了,根节点的元素是最大的元素。这样的堆叫做最大堆,相反如果任意一个节点小于等于他的孩子节点,那就是最小堆。这里要注意:不是越贴近根节点的值就越大。
由于最大堆是完全二叉树,那么最大堆就可以用数组来作为底层实现。如图所示,编号 1 -10 就代表一个数组的索引,或者用 0 - 9 也 OK。
如果用 1 -10 索引来表示的话,比如 41 这个元素,索引为 2,他的左孩子索引就是 4(i x 2),右孩子节点就是 5(i x 2 + 1)。
相反,知道左孩子或者右孩子,求父节点直接除 2 就可以了,4 / 2,5 / 2 强转为 int 之后都是 2。
如果用 0 - 9 索引表示这些元素,已知父亲节点索引为 1,左孩子节点就是 4(i x 2 + 1),右孩子节点是 5(i x 2 + 2),知道左孩子或右孩子索引 3 和 4,父节点索引就是 1(i – 1)/ 2。
知道了这些特点,开始用代码实现一个最大堆
// 使用数组当作底层数据结构
public MyArray<E> myArray;
public MaxHeap(int capacity){myArray = new MyArray<>(capacity);
}
public MaxHeap(){myArray = new MyArray<>();
}
// 父节点的索引 (i-1)/2
public int parent(int index){if(index == 0)
throw new IllegalArgumentException("index:0,doesn't hava parent.");
return (index - 1) / 2;
}
// 左孩子节点 i\*2+1
public int leftChild(int index){return index \* 2 + 1;}
// 右孩子节点 i\*2+2
public int rightChild(int index){return index \* 2 + 2;}
添加一个节点
添加节点的时候,要满足最大堆的性质需要遵从两点,第一就是要添加到数组末尾的位置,满足完全二叉树的特性。第二就是满足每一个节点要比他的孩子节点要大的特性,52 添加到末尾后,要不断的向上寻找父节点,和父节点比较大小后,和父节点元素做交换操作,找到自己合适的位置,我们把这个操作称为 ShiftUp(上浮)
public void add(E e){myArray.addLast(e);
shiftUp(myArray.getSize() - 1);
}
private void shiftUp(int index){
// 把当前 index 的值和父节点的值做比较,小于父节点就向上移动
while(index > 0 && myArray.getByIndex(index).compareTo(myArray.getByIndex(parent(index))) > 0)
{
// 对两个索引交换
myArray.swap(index,parent(index));
// 重新标记 index 位置,用于下次交换逻辑
index = parent(index);
}
}
取出根元素
如果想取出根元素 62,取出后索引为 0 的位置就为空了,为了满足最大堆的结构,就需要重新组织这颗二叉树。我们采用将最后一个元素放到根元素的位置,然后再根据这个元素,不断向下去判断自己是不是比两个孩子节点都大,如果大就不需要移动。如果比孩子节点小,就向下挪动,因为有两个孩子,还需要比较这两个孩子谁更大,谁大就和谁交换。这个过程叫做 shift down(下沉)。
// 取出最大的元素
public E extractMax()
{E max = findMax();
myArray.swap(0,myArray.getSize() - 1);
myArray.removeLast();
shiftDown(0);
return max;
}
// 查看一下最大元素是谁
public E findMax()
{if(myArray.getSize() == 0)
throw new IndexOutOfBoundsException("heap is empty.");
return myArray.getByIndex(0);
}
private void shiftDown(int index) {
// 如果一个元素的左孩子大于了总数量,那么就结束
while (leftChild(index) < myArray.getSize()) {
// 判断有右孩子的情况下,在与左孩子做比较
int swapIndex = leftChild(index); // 默认是左孩子大
//// 如果有右孩子并且右孩子比左孩子大
if (swapIndex + 1 < myArray.getSize() &&
myArray.getByIndex(swapIndex).compareTo(myArray.getByIndex(swapIndex + 1)) < 0) {swapIndex = rightChild(index);
}
// 堆的性质:只要当前的父亲节点大于两个孩子节点即可,不需要一直往下看,直接结束循环
if (myArray.getByIndex(index).compareTo(myArray.getByIndex(swapIndex)) > 0) {break;}
myArray.swap(index, swapIndex);// 和子节点交换元素
index = swapIndex;// 重新标记 index 的位置,便于下次循环逻辑
}
}
Replace 操作
replace 就是替换根元素的操作,简单的思路可以是先取出根元素,也就是上面实现的 extractMax() 方法,然后在添加一个元素。但这样相当于两个 O(logn) 的操作。还有一种实现思路就是直接将根元素替换掉,然后做一个 shift down 就解决了。
// 取出根元素,并替换成最新元素
public E replace(E e) {E e1 = findMax();
myArray.set(0,e);
shiftDown(0);
return e1;
}
Heapify 操作
heapify 是将一个数组转换为一个堆的过程,这个实现完全可以用添加操作来完成,但是复杂度是 O(nlogn) 级别的,如果将一个数组一次性的放到堆中,找到最后一个非叶子节点,从这个节点向前遍历,将每一个元素做一个下沉操作就可以了。那如何定位最后一个非叶子节点呢?很简单就是最后一个叶子节点的父节点。
public MaxHeap(E[] arr){
// 将一个数组直接转换为最大堆
myArray = new MyArray<>(arr);
//parent(arr.getSize - 1) 是除了叶子节点以外,开始向上遍历
for(int x = parent(myArray.getSize() - 1); x >= 0 ; x--) {shiftDown(x);
}
}
D 叉堆
二叉堆是一个节点有两个儿子,D 叉堆就是一个节点有 D 个儿子,这样树的深度就会变短。用法和二叉堆差不多,只不过元素在上浮和下沉的时候需要多判断一下。至于 D 取值为多少性能最好,还是要实战的试一下的。