Min Heap 最小堆
最小堆能够动态地维护一组有序数据，使得最小的元素始终位于堆顶。堆也是优先队列的底层实现方式
什么是堆?
宏观来说, 堆能够动态地维护一组有序数据，使得最小或最大的元素始终位于堆顶. 对于最小堆来说, 最小的元素位于堆顶. 对于最大堆来说, 最大的元素位于堆顶
从数据结构角度来说, 堆是一个完全二叉树. 对于最小堆来说, 每一个父节点都比子节点元素要小. 对于最大堆
什么是完全二叉树?
完全二叉树就是所有节点按照从上到下, 从左到右的顺序排列,中间不能有空.
最小堆的定义:
最小堆是一个完全二叉树, 最小的元素位于堆顶, 父亲节点比孩子节点要小. 可以用下面这幅图来表示:
红色的节点为堆顶节点, 节点旁边的序号表示节点的序号.
很显然我们可以发现父节点和其字节点的索引规律:
父节点= (子节点-1)/2
左孩子=2*父节点+1
右孩子=2*父节点+2
我们可以用一个数组将堆表示出来
索引
0
1
2
3
4
5
6
7
元素
6
7
12
9
8
13
14
10
实现最小堆
根据上面所说,我们可以用数组表示堆, 于是很轻易地写出最小堆的构造函数
public class MinHeap<E extends Comparable<E>> {
private Array<E> data;
public MinHeap(int capacity){
data=new Array<>(capacity);
}
public MinHeap(){
data=new Array<>();
}
}我们用到了前面章节实现的 Array 动态数组作为堆的底层实现
一些简单的方法
我们实现了一些堆中常用的简单方法
getSize() 获取堆中元素个数
isEmpty判断堆是否为空
parent(index) 获取父节点的索引
leftChild(index) 获取左孩子的索引
rightChild(index)获取右孩子的索引
swap(int idx1, int idx) 交换两个元素
findMin()获得堆顶元素
isLeaf()判断某一个节点是否为叶子节点
public int getSize(){
return data.getSize();
}
boolean isEmpty(){
return data.isEmpty();
}
private int parent(int index){
if (index==0){
throw new IllegalArgumentException("index-0 doesn't have parent. ");
}
return (index-1)/2;
}
private int leftChild(int index){
return index*2+1;
}
private int rightChild(int index){
return index*2+2;
}
private void swap(int idx1, int idx2){
E temp=data.get(idx1);
data.set(idx1,data.get(idx2));
data.set(idx2,temp);
}
public E findMin(){
if (data.isEmpty()){
throw new IllegalArgumentException("Cannot findMin when the heap is empty!");
}
return data.get(0);
}
//判断某个节点是否为叶子节点
public boolean isLeaf(int idx){
//如果左孩子索引越界,说明没有左孩子,连左孩子都没有肯定是叶子节点
return leftChild(idx)< data.getSize();
}shiftUp 和 shiftDown
shiftUp 与 shiftDown 是堆的核心操作, 堆的性质主要靠这两个操作进行维护.
先说 shiftUp 操作. shiftUp操作的原理非常简单, 将一个节点与父节点进行比较, 若比父节点小, 则与父节点交换. 如此循环, 直到到达根节点. 这个道理也非常简单, 就是保证父节点比孩子节点要小, 最小的元素一定要放在堆顶, 也就是根节点.
private void shiftUp(int idx){
while (idx>0 ){//只要没有达到根节点, 就继续尝试与父节点交换
//如果父节点更大, 就与父节点进行交换
if (data.get(parent(idx)).compareTo(data.get(idx))>0){
swap(idx,parent(idx));
idx=parent(idx);
}else {//否则, 跳出循环
break;
}
}
}再说shiftDown操作. shiftDown操作就是将一个元素不断地与左右孩子的较小节点进行比较, 若父节点更小, 则进行交换, 直到到达了叶子节点. 这个道理和shiftUp相同, 就是保证父节点比孩子节点要小, 最小的元素一定要放在堆顶, 也就是根节点.
private void shiftDown(int idx){
while (isLeaf(idx)){//到了叶子节点就不用再shiftDown了,跳出循环
int j=leftChild(idx);//j初始为左孩子索引
if ((j+1)<data.getSize()){//说明有右孩子
//而且右孩子比左孩子更小, 那就和右孩子交换
if (data.get(j+1).compareTo(data.get(j))<0){
j++;//j更新为右孩子索引
}
}
//data[j]是idx节点左右孩子的最小值
//如果 data[idx] 比 data[j] 还要小,就不需要向下交换了, 直接跳出循环
if (data.get(idx).compareTo(data.get(j))<0){
break;
}
//否则交换 data[idx] 和 data[j], 接着向下shiftdown
swap(idx,j);
idx=j;
}
}接口方法
有了上面的辅助方法, 我们可以来写一些常用的接口方法
add(E e) 向堆中添加元素
向堆中添加元素非常简单, 分为两步
直接向数组末尾添加新元素
对数组末尾元素进行 shiftUp 操作
用图表示如下
代码表示如下:
public void add(E e){
data.addLast(e);
shiftUp(data.getSize()-1);
}extractMin() 取出堆顶元素
取出堆顶也元素非常简单, 分为4步
堆顶元素备份出来
用数组中最后一个元素替代堆顶元素
对新的堆顶元素进行shiftDown操作
返回原来的堆顶元素
用图表示如下
代码表示如下:
public E extractMin(){
E ret=findMin();
swap(0,data.getSize()-1);
data.removeLast();
shiftDown(0);
return ret;
}replace(E e) 取出堆顶元素并传入新的堆顶元素
代码逻辑和上面类似, 直接给出代码:
//取出最小值,并且替换成e
public E replace(E e){
E ret=findMin();
data.set(0,e);
shiftDown(0);
return ret;
}heapify 操作
heapify 表示根据一个数组构造一个堆
我们先将数组元素提取出来, 再维护最小堆的性质(父节点始终比孩子节点要小). 为此, 我们需要从倒数第一个非叶子节点开始, 对每一个元素执行shiftDown 操作, 直到根节点. 这个道理也非常简单, 叶子节点是没有办法进行shiftDown操作的.
//heapify 操作, 传入一个数组, 根据这个数组构造出一个最小堆
public MinHeap(E[] arr){
data=new Array(arr.length);
for (int i = 0; i < arr.length; i++) {
data.addLast(arr[i]);
}
for (int i = parent(arr.length-1); i >=0 ; i--) {
shiftDown(i);
}
}至此, 我们完成了一个最小堆的所有操作
测试一下
我们用两个堆进行了测试, 一个是通过向堆中加入新元素再取出堆顶元素, 另一个是根据一个数组构造一个堆,再进行取出堆顶元素.
堆中取出的元素放入数组当中, 通过遍历数组, 判断数组是否有序来判断堆是否正确.
public static void main(String[] args) {
int n=1000;
Random random=new Random();
//测试向空堆里面添加元素, 删除元素
MinHeap<Integer> minHeap1=new MinHeap<>();
for (int i = 0; i < n; i++) {
minHeap1.add(random.nextInt(Integer.MAX_VALUE));
}
int[] arr1=new int[n];
for (int i = 0; i < n; i++) {
arr1[i]= minHeap1.extractMin();
}
for (int i = 1 ; i <n ; i++) {
if (arr1[i-1]>arr1[i]){
throw new IllegalArgumentException("MinHeap erro !");
}
}
//测试将一个数组构造成一个堆
//随机数组
Integer[] arr2=new Integer[n];
for (int i = 0; i < n; i++) {
arr2[i]=random.nextInt(Integer.MAX_VALUE);
}
//heapify操作
MinHeap<Integer> minHeap2=new MinHeap<>(arr2);
for (int i = 0; i < n; i++) {
arr2[i]= minHeap2.extractMin();
}
for (int i = 1 ; i <n ; i++) {
if (arr2[i-1]>arr2[i]){
throw new IllegalArgumentException("MinHeap erro !");
}
}
System.out.println("Test MinHeap completed!");
}
}测试结果和我们预想的一下, 输出:
Test MinHeap completed!
Process finished with exit code 0Last updated
Was this helpful?