系统提供的堆 VS 手动改写堆

要求：在一个已经组织好的大根堆或者小根堆中，更改其中的某个值后，仍要求其为大根堆或者小根堆
为啥系统提供的堆实现不了，因为系统提供的堆结构不会记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{
		private ArrayList heap;
		// 为啥系统实现不了，自己手动改写后能实现，关键在于indexMap表
		// 任何一个你给我的样本T，记录着它在堆heap上的什么位置Integer
		private HashMap indexMap;
		private int heapSize;
		// 告诉我关于样本类型T的比较器comparator
		// 有了这个比较器就知道如何比较大小了
		private Comparator comparator;
		
		public MyHeap(Comparator 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{

		@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 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 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);
		}
	}
}