当前位置:网站首页>系统提供的堆 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);
}
}
}
边栏推荐
猜你喜欢
h264协议
一甲子,正青春,CCF创建六十周年庆典在苏州举行
软件测试——金融测试类面试题,看完直接去面试了
放下手机吧:实验表明花20分钟思考和上网冲浪同样快乐
Information system project managers must memorize the core test sites (63) The main process of project portfolio management & DIPP analysis
阿里高工带来的20022最新面试总结太香了
[Interview high-frequency questions] Linked list high-frequency questions that can be gradually optimized
曼城推出可检测情绪的智能围巾,把球迷给整迷惑了
MongoDB-查询中$all的用法介绍
鹅厂机器狗花式穿越10m梅花桩:前空翻、单桩跳、起身作揖...全程不打一个趔趄...
随机推荐
electron 应用开发优秀实践
又有大厂员工连续加班倒下/ 百度搜狗取消快照/ 马斯克生父不为他骄傲...今日更多新鲜事在此...
在北极都可以穿短袖了,温度飙升至32.5℃
一甲子,正青春,CCF创建六十周年庆典在苏州举行
腾讯欲成育碧最大股东/ 米哈游招NLP内容生成研究员/ AI发现四千余物种濒临灭绝...今日更多新鲜事在此...
Reading and writing after separation, performance were up 100%
Manchester city launch emotional intelligence scarf can be detected, give the fans
Two ways to enter the Oracle database
Byte Qiu Zhao confused me on both sides, and asked me under what circumstances would the SYN message be discarded?
Modify the VOT2018.json file and remove the color in the image path
你没见过的《老友记》镜头,AI给补出来了|ECCV 2022
Simple understanding of ThreadLocal
Win10 compiles the x264 library (there are also generated lib files)
国产抗新冠口服药每瓶不超300元/ 我国IPv6网络全面建成/ 谷歌入局折叠屏手机...今日更多新鲜事在此...
8、IDEA提交代码出现: Fetch failed fatal: Could not read from remote repository
研发需求的验收标准应该怎么写? | 敏捷实践
西湖大学教授怎么看AI制药革命?|量子位智库圆桌实录
从零开始Blazor Server(9)--修改Layout
阿里高工带来的20022最新面试总结太香了
WPF implements a MessageBox message prompt box with a mask