Java语言实现最大堆代码示例
作者:GoldArowana 时间:2021-09-22 14:20:44
最大堆
最大堆的特点是父元素比子元素大,并且是一棵完全二叉树。
data[1]开始存,data[0]空着不用。也可以把data[0]当成size来用。
public class MaxHeap<T extends Comparable<? super T>> {
private T[] data;
private int size;
private int capacity;
public MaxHeap(int capacity) {
this.data = (T[]) new Comparable[capacity + 1];
size = 0;
this.capacity = capacity;
}
public int size() {
return this.size;
}
public Boolean isEmpty() {
return size == 0;
}
public int getCapacity() {
return this.capacity;
}
/**
* @return 查看最大根(只看不删, 与popMax对比)
*/
public T seekMax() {
return data[1];
}
public void swap(int i, int j) {
if (i != j) {
T temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
public void insert(T item) {
size++;
data[size] = item;
shiftUp(size);
}
/**
* @return 弹出最大根(弹出意味着删除, 与seekMax对比)
*/
public T popMax() {
swap(1, size--);
shiftDown(1);
return data[size + 1];
}
/**
* @param child 孩子节点下角标是child,父节点下角表是child/2
*/
public void shiftUp(int child) {
while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {
swap(child, child / 2);
child = child / 2;
}
}
/**
* @param a data数组中某个元素的下角标
* @param b data数组中某个元素的下角标
* @return 哪个元素大就返回哪个的下角标
*/
private int max(int a, int b) {
if (data[a].compareTo(data[b]) < 0) {
//如果data[b]大
return b;
//返回b
} else {
//如果data[a]大
return a;
//返回a
}
}
/**
* @param a data数组中某个元素的下角标
* @param b data数组中某个元素的下角标
* @param c data数组中某个元素的下角标
* @return 哪个元素大就返回哪个的下角标
*/
private int max(int a, int b, int c) {
int biggest = max(a, b);
biggest = max(biggest, c);
return biggest;
}
/**
* @param father 父节点下角标是father,左右两个孩子节点的下角表分别是:father*2 和 father*2+1
*/
public void shiftDown(int father) {
while (true) {
int lchild = father * 2;
//左孩子
int rchild = father * 2 + 1;
//右孩子
int newFather = father;
//newFather即将更新,父、左、右三个结点谁大,newFather就是谁的下角标
if (lchild > size) {
//如果该father结点既没有左孩子,也没有右孩子
return;
} else if (rchild > size) {
//如果该father结点只有左孩子,没有右孩子
newFather = max(father, lchild);
} else {
//如果该father结点既有左孩子,又有右孩子
newFather = max(father, lchild, rchild);
}
if (newFather == father) {
//说明father比两个子结点都要大,表名已经是大根堆,不用继续调整了
return;
} else {
//否则,还需要继续调整堆,直到满足大根堆条件为止
swap(father, newFather);
//值进行交换
father = newFather;
//更新father的值,相当于继续调整shiftDown(newFather)
}
}
}
public static void main(String[] args) {
//创建大根堆
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
//向堆里存
for (int i = 0; i < 100; i++) {
maxHeap.insert((int) (Math.random() * 100));
}
//创建数组
Integer[] arr = new Integer[100];
//从堆里取,放进数组里
for (int i = 0; i < 100; i++) {
arr[i] = maxHeap.popMax();
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
最大堆:shiftDown()函数与上面不一样
public class MaxHeap<T extends Comparable<? super T>> {
private T[] data;
private int size;
private int capacity;
public MaxHeap(int capacity) {
data = (T[]) new Comparable[capacity + 1];
this.capacity = capacity;
size = 0;
}
public int size() {
return size;
}
public Boolean isEmpty() {
return size == 0;
}
public void insert(T item) {
data[size + 1] = item;
size++;
shiftUp(size);
}
/**
* @return 弹出最大根(弹出意味着删除, 与seekMax对比)
*/
public T popMax() {
T ret = data[1];
swap(1, size);
size--;
shiftDown(1);
return ret;
}
/**
* @return 查看最大根(只看不删, 与popMax对比)
*/
public T seekMax() {
return data[1];
}
public void swap(int i, int j) {
if (i != j) {
T temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
public void shiftUp(int k) {
while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
swap(k, k / 2);
k /= 2;
}
}
public void shiftDown(int father) {
while (2 * father <= size) {
int newFather = 2 * father;
if (newFather + 1 <= size && data[newFather + 1].compareTo(data[newFather]) > 0) {
//data[j] data[j+1]两者取大的那个
newFather = newFather + 1;
}
if (data[father].compareTo(data[newFather]) >= 0) {
break;
} else {
swap(father, newFather);
//值进行交换
father = newFather;
//newFather是(2*father)或者是(2*father+1),也就是继续shiftDown(newFather);
}
}
}
public static void main(String[] args) {
//创建大根堆
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
//向堆里存
for (int i = 0; i < 100; i++) {
maxHeap.insert((int) (Math.random() * 100));
}
//创建数组
Integer[] arr = new Integer[100];
//从堆里取,放进数组里
for (int i = 0; i < 100; i++) {
arr[i] = maxHeap.popMax();
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
来源:http://www.cnblogs.com/noKing/p/7954898.html
标签:java,最大堆
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Java中Json字符串直接转换为对象的方法(包括多层List集合)
2021-06-26 18:13:42
C#实现把彩色图片灰度化代码分享
2022-04-21 18:11:33
Spring Native项目实战(体验79毫秒启动springboot应用)
2022-03-14 22:18:42
![](https://img.aspxhome.com/file/2023/1/78361_0s.png)
C#实现XML文件与DataTable、Dataset互转
2021-06-07 04:00:27
java实现手写一个简单版的线程池
2022-09-29 04:59:32
![](https://img.aspxhome.com/file/2023/6/62726_0s.jpg)
JavaSE static final及abstract修饰符实例解析
2021-07-01 10:54:54
![](https://img.aspxhome.com/file/2023/9/62129_0s.png)
代码详解Java猴子选王问题(约瑟夫环)
2023-09-16 07:33:43
SpringBoot集成ElasticSearch的示例代码
2023-05-02 05:50:28
Android 限制edittext 整数和小数位数 过滤器(详解)
2023-11-24 17:33:52
C#队列的简单使用
2022-01-21 03:05:42
![](https://img.aspxhome.com/file/2023/9/96319_0s.png)
C#中使用CAS实现无锁算法的示例详解
2023-07-01 20:57:44
springboot 同时启用http/https的配置方法
2023-06-22 12:04:12
![](https://img.aspxhome.com/file/2023/2/108422_0s.png)
windows下C#定时管理器框架Task.MainForm详解
2021-06-06 13:59:06
![](https://img.aspxhome.com/file/2023/0/83240_0s.png)
C#入门之定义类成员与接口实现
2023-05-25 09:50:58
Java 反射机制实例详解
2023-11-28 03:49:47
Java开发学习 Eclipse项目有红感叹号解决之道
2022-10-22 15:29:27
IDEA内存调试插件(好用)
2022-04-19 08:51:13
![](https://img.aspxhome.com/file/2023/3/108413_0s.jpg)
WPF实现动画效果
2023-06-26 17:49:44
![](https://img.aspxhome.com/file/2023/3/83303_0s.jpg)
java实现静默加载Class示例代码
2023-12-18 22:06:52
SpringSecurity注销设置的方法
2023-08-05 20:46:15
![](https://img.aspxhome.com/file/2023/0/92540_0s.jpg)