当前位置:网站首页>系统提供的堆 VS 手动改写堆
系统提供的堆 VS 手动改写堆
2022-08-09 12:01:00 【爱敲代码的Harrison】
要求:在一个已经组织好的大根堆或者小根堆中,更改其中的某个值后,仍要求其为大根堆或者小根堆
为啥系统提供的堆实现不了,因为系统提供的堆结构不会记indexMap这张反向表。但是如果系统增加了这张反向表,实现代价又会很高,而且系统也不确定你会不会用到这些功能,所以系统干脆不提供了,大量的情况就是这样。但是不排除某种语言中有这个功能(也就是有resign()这个方法),但是C++跟Java中是没有的,所以这种情况下需要自己手动改写堆结构!
具体请看下面代码和运行结果吧!
package com.harrison.class04;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
public class Code06_HeapGreater {
public static class MyHeap<T>{
private ArrayList<T> heap;
// 为啥系统实现不了,自己手动改写后能实现,关键在于indexMap表
// 任何一个你给我的样本T,记录着它在堆heap上的什么位置Integer
private HashMap<T, Integer> indexMap;
private int heapSize;
// 告诉我关于样本类型T的比较器comparator
// 有了这个比较器就知道如何比较大小了
private Comparator<? super T> comparator;
public MyHeap(Comparator<? super T> com) {
heap=new ArrayList<>();
indexMap=new HashMap<>();
heapSize=0;
comparator=com;
}
public boolean isEmpty() {
return heapSize==0;
}
public int size() {
return heapSize;
}
public boolean contains(T key) {
return indexMap.containsKey(key);
}
public void push(T value) {
heap.add(value);
indexMap.put(value, heapSize);
heapInsert(heapSize++);
}
public void heapInsert(int index) {
// 比较器告诉你 你自己跟父结点如何比较大小
while(comparator.compare(heap.get(index), heap.get((index-1)/2))<0){
swap(index, (index-1)/2);
index=(index-1)/2;
}
}
public T pop() {
T ans=heap.get(0);
int end=heapSize-1;
swap(0, end);
// 移除的是堆中的位置!!不是样本!!!
heap.remove(end);
indexMap.remove(ans);
heapify(0, --heapSize);
return ans;
}
public void heapify(int index,int heapSize) {
int left=index*2+1;
while(left<heapSize) {
int largest=(left+1<heapSize &&
comparator.compare(heap.get(left+1), heap.get(left))<0
)?left+1:left;
int allLargest=comparator.compare(heap.get(largest), heap.get(index))<0
?largest:index;
if(allLargest==index) {
break;
}
swap(allLargest, index);
index=allLargest;
left=2*index+1;
}
}
// 关键方法:为什么在一个大根堆或者小根堆中更改某个值后,仍然能调整为大根堆或小根堆
// 用户要求改变堆中的某个值,但是没告诉我们这个值应该是往上移动还是往下移动
// 通过indexMap表找到样本在堆中的哪个位置,然后调整为大根堆或小根堆
public void resign(T value) {
int valueIndex=indexMap.get(value);
// 两个方法只会中一个
heapInsert(valueIndex);
heapify(valueIndex, heapSize);
}
// 在堆和indexMap表中交换i位置和j位置的数
// heap有任何变换,indexMap表都要跟着一起变,保证两个结构强同步
public void swap(int i, int j) {
T o1=heap.get(i);
T o2=heap.get(j);
heap.set(i, o2);
heap.set(j, o1);
indexMap.put(o2, i);
indexMap.put(o1, j);
}
}
public static class Student{
public int classNo;
public int age;
public int id;
public Student(int c,int a,int i) {
classNo=c;
age=a;
id=i;
}
}
public static class StudentComparator implements Comparator<Student>{
@Override
public int compare(Student o1, Student o2) {
// TODO Auto-generated method stub
return o1.age-o2.age;
}
}
public static void main(String[] args) {
System.out.println("系统提供的堆:");
Student s1=null;
Student s2=null;
Student s3=null;
Student s4=null;
Student s5=null;
Student s6=null;
s1=new Student(2, 50, 11111);
s2=new Student(1, 60, 22222);
s3=new Student(6, 10, 33333);
s4=new Student(3, 20, 44444);
s5=new Student(7, 72, 55555);
s6=new Student(1, 14, 66666);
PriorityQueue<Student> heap=new PriorityQueue<>(new StudentComparator());
heap.add(s1);
heap.add(s2);
heap.add(s3);
heap.add(s4);
heap.add(s5);
heap.add(s6);
while(!heap.isEmpty()) {
Student cur=heap.poll();
System.out.println(cur.classNo+","+cur.age+","+cur.id);
}
System.out.println("======================");
System.out.println("手动改写的堆:");
MyHeap<Student> myHeap=new MyHeap<>(new StudentComparator());
myHeap.push(s1);
myHeap.push(s2);
myHeap.push(s3);
myHeap.push(s4);
myHeap.push(s5);
myHeap.push(s6);
while(!myHeap.isEmpty()) {
Student cur=myHeap.pop();
System.out.println(cur.classNo+","+cur.age+","+cur.id);
}
System.out.println("======================");
System.out.println("系统提供的堆(改了堆中某些值):");
s1=new Student(2, 50, 11111);
s2=new Student(1, 60, 22222);
s3=new Student(6, 10, 33333);
s4=new Student(3, 20, 44444);
s5=new Student(7, 72, 55555);
s6=new Student(1, 14, 66666);
heap=new PriorityQueue<>(new StudentComparator());
heap.add(s1);
heap.add(s2);
heap.add(s3);
heap.add(s4);
heap.add(s5);
heap.add(s6);
s2.age=6;
s4.age=12;
s5.age=10;
s6.age=84;
while(!heap.isEmpty()) {
Student cur=heap.poll();
System.out.println(cur.classNo+","+cur.age+","+cur.id);
}
System.out.println("======================");
System.out.println("手动改写的堆(改了堆中某些值):");
s1=new Student(2, 50, 11111);
s2=new Student(1, 60, 22222);
s3=new Student(6, 10, 33333);
s4=new Student(3, 20, 44444);
s5=new Student(7, 72, 55555);
s6=new Student(1, 14, 66666);
myHeap=new MyHeap<>(new StudentComparator());
myHeap.push(s1);
myHeap.push(s2);
myHeap.push(s3);
myHeap.push(s4);
myHeap.push(s5);
myHeap.push(s6);
s2.age=6;
myHeap.resign(s2);
s4.age=12;
myHeap.resign(s4);
s5.age=10;
myHeap.resign(s5);
s6.age=84;
myHeap.resign(s6);
while(!myHeap.isEmpty()) {
Student cur=myHeap.pop();
System.out.println(cur.classNo+","+cur.age+","+cur.id);
}
}
}
边栏推荐
- 软件测试——金融测试类面试题,看完直接去面试了
- The core key points of microservice architecture
- GPT-3组合DALL·E,60秒内搞定游戏设定和原型动画!网友看后:这游戏想玩
- 已解决IndentationError: unindent does not match any oute r indentation Level
- 脱光衣服待着就能减肥,当真有这好事?
- proto3-2 syntax
- 张朝阳对话俞敏洪:一边是手推物理公式,一边是古诗信手拈来
- 你没见过的《老友记》镜头,AI给补出来了|ECCV 2022
- Shell正则表达式,三剑客之grep命令
- Golang学习之路(五):Golang的函数
猜你喜欢
900页数学论文证明旋转的黑洞不会爆炸,丘成桐:30多年来广义相对论首次重大突破...
ABAP 面试题:如何使用 ABAP 编程语言的 System CALL 接口,直接执行 ABAP 服务器所在操作系统的 shell 命令?
【微服务~远程调用】整合RestTemplate、WebClient、Feign
MySQL 原理与优化,Group By 优化 技巧
你没见过的《老友记》镜头,AI给补出来了|ECCV 2022
又有大厂员工连续加班倒下/ 百度搜狗取消快照/ 马斯克生父不为他骄傲...今日更多新鲜事在此...
基于CAP组件实现补偿事务与幂等性保障
Senior told me that the giant MySQL is through SSH connection
h264协议
WeChat side: what is consistent hashing, usage scenarios, and what problems does it solve?
随机推荐
Adalvo acquires its first branded product, Onsolis
redis库没法引入
金融业“限薪令”出台/ 软银出售过半阿里持仓/ DeepMind新实验室成立... 今日更多新鲜事在此...
索引index
数字化转型之支撑保障单元
虚拟机安装出现的问题汇总
WPF 实现带蒙版的 MessageBox 消息提示框
JD.com architects tidy up: what are the core technical knowledge points of jvm and performance tuning
OpenSSF的开源软件风险评估工具:Scorecards
PM2 configuration file
【Untitled】
We really need DApp?Really can't meet our fantasy App?
API调用,API传参,面向对接开发,你真的会写接口文档吗?
超越CLIP的多模态模型,只需不到1%的训练数据!南加大最新研究来了
Batch大小不一定是2的n次幂!ML资深学者最新结论
1-hour live broadcast recruitment order: industry big names share dry goods, and enterprise registration opens丨qubit·viewpoint
问题来了:4GB物理内存的机器上申请8G内存能成功吗?
The batch size does not have to be a power of 2!The latest conclusions of senior ML scholars
发明时代,「幂集创新」事关你我
C# 获取系统已安装的.NET版本