优先队列之二叉堆(JAVA实现)
程序员文章站
2022-06-06 20:55:41
...
一、定义:
1.完全二叉树(除了最后一层可能不饱和,其他都饱和,且最后一层节点是从左往右排满)
2.堆性:父节点要小于等于(最小堆)或者大于等于(最大堆)子节点。
二叉堆由于是完全二叉树,故父节点和子节点的位置存在一定的关系。若将二叉堆的第一个元素放在数组索引为1的位置,父节点和子节点的位置关系如下:
1. 索引为i的左孩子的索引是 (2*i);
2. 索引为i的左孩子的索引是 (2*i+1);
3. 索引为i的父结点的索引是 (i/2)
故我们一般通过数组来实现二叉堆。
通过上述定义可知,“最大堆”和“最小堆”是对称关系。本文以最小堆为例进行描述。
二、实现思路:
1.插入(上滤)
- a.为将一个元素 X 插入到堆中,我们在下一个可用位置创建一个空穴(初始为堆的末尾,结构性)。
- b. 如果 X 可以放在该空穴中而不破坏堆的序,那么插入完成。
- c.如果不能,我们把空穴的父节点上的元素移入该空穴中,这样,空穴就朝着根的方向上冒一步。
-
d.继续b,c的过程直到 X 能被放入空穴中为止。
如下图:演示将元素14插入二叉堆的过程
2.删除根元素(最小值/最大值)(下滤)
- a.将根节点删除,使之成为空穴(由于现在堆少了一个元素,因此堆中最后一个元素 X 必须移动到该堆的某个地方,结构性)。
- b.如果 X 可以直接被放到空穴中,那么 deleteMin 完成。
- c.如果不可以,将空穴的两个儿子中比较小者移入空穴,这样就把空穴向下推了一层。
-
d.重复b,c 直到 X 可以被放入空穴中。
如下图:演示将根元素13删除的过程
3.创建:
a.简单的我们可以认为它可以使用N个相继的insert操作来完成。每个insert最坏时间为O(logN),则其构建时间为O(N)。
b.更为常用的算法是先保持其结构性,之后再通过检查每个位置,下滤操作使其满足堆序性。如下:
一开始满足结构性,但是并不满足堆序性,我们在元素70的位置进行下滤操作。
三、代码实现
import java.util.ArrayList;
/**
* 头元素存储于1位置
* i节点的左二子位置2*i 右儿子位置2*i+1 父亲位置i/2
*/
public class BinaryHeap<T extends Comparable<T>> {
/**
* 由于java禁止使用泛型数组,故此处使用ArrayList存储信息
*/
private ArrayList<T> array;//
private int currentSize;//大小
public BinaryHeap() {
array = new ArrayList<>();
array.add(null);
}
/**
* 将数组转化为二叉堆
*
* @param array
*/
public BinaryHeap(ArrayList<T> array) {
currentSize = array.size();
int i = 1;
for (T t : array) {//保证结构性
this.array.set(i++, t);
}
//保证堆性 下滤
for (i = currentSize / 2; i > 0; i--) {
percolateDown(i);
}
}
/**
* 插入
*
* @param x
*/
public void insert(T x) {
int hole = currentSize + 1;//空穴的初始位置
array.add(x);
//当x元素小于空穴的父节点时,空穴进行上滤
for (; hole > 1 && x.compareTo(array.get(hole / 2)) < 0; hole = hole / 2) {
array.set(hole, array.get(hole / 2));
}
//当x元素不小于空穴的父节点元素时,找到合适的位置,放入
array.set(hole, x);
currentSize++;
}
/**
* 查找最小元素
*
* @return
*/
public T findMin() {
return array.get(1);
}
/**
* 删除最小元素
*
* @return
*/
public T deleteMin() {
if (currentSize < 1) {
System.out.println("BinaryHeap is Empty");
}
T minElement = array.get(1);//获取最小元素
array.set(1, array.get(currentSize));//将末尾元素存入
array.remove(currentSize--);//移除最后元素,并使大小-1
if (currentSize > 0) {
percolateDown(1);//下滤
}
return minElement;
}
/**
* 删除任一元素
*
* @return 元素不存在,返回-1
* 删除成功,返回该元素的下标
*/
public int delete(T x) throws Exception {
if (currentSize < 1) {
throw new Exception("BinaryHeap is Empty");
}
int index = array.indexOf(x);//获取x的索引
if (index == -1) {
return -1;
}
array.set(index, array.get(currentSize));
array.remove(currentSize--);
percolateDown(index);//下滤
return index;
}
/**
* 下滤
*/
public void percolateDown(int hole) {
int child;
T temp = array.get(hole);//需要下滤的元素,临时存储
for (; hole * 2 <= currentSize; hole = child) {
child = hole * 2;
//child不为最后一个元素,且右元素小于左元素时:child为右元素,否则child为左元素
if (child < currentSize && array.get(child).compareTo(array.get(child + 1)) > 0) {
child++;
}
if (temp.compareTo(array.get(child)) > 0) {//temp大于较小的元素 ,将空穴下滤一层
array.set(hole, array.get(child));
} else {
break;//找到合适的位置,跳出循环替换
}
}
array.set(hole, temp);
}
public static void main(String[] args) {
int numItems = 1000;
BinaryHeap<Integer> h = new BinaryHeap<>();
int i = 37;
for (i = 37; i != 0; i = (i + 37) % numItems) {
h.insert(i);
}
for (i = 1; i < numItems; i++) {
if (h.deleteMin() != i)
System.out.println("Oops! " + i);
}
}
}
推荐阅读
-
Java实现二叉树的深度优先遍历和广度优先遍历算法示例
-
Java之使用链表实现队列
-
用Python实现数据结构之优先级队列
-
剑指offer之队列中的最大值(C++/Java双重实现)
-
并发编程(十)—— Java 并发队列 BlockingQueue 实现之 SynchronousQueue源码分析
-
Java实现最大二叉堆中找min<=x
-
Java实现最大二叉堆中找min<=x
-
一种优先队列的实现(基于二叉堆)
-
JAVA利用优先队列PriorityQueue+ConcurrentHashMap实现带过期时间的LRU
-
并发编程(八)—— Java 并发队列 BlockingQueue 实现之 ArrayBlockingQueue 源码分析