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

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