[数据结构与算法]系统提供的堆 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<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);
		}
	}
}