手动改写堆（非常重要）

1. 已经入堆的元素，如果参与排序的指标方法变化，系统提供的堆无法做到时间复杂度 O ( l o g N ) O(logN) O(logN) 调整，都是 O ( N ) O(N) O(N) 调整！
2. 系统提供的堆只能弹出栈顶，做不到自由删除任何一个堆中的元素，或者说，无法在时间复杂度 O ( l o g N ) O(logN) O(logN) 内完成！一定会高于 O ( l o g N ) O(logN) O(logN)！根本原因是：无反向索引表

解释：一个数组 arr，其中存放的元素是 [a, b, c]，可以知道 0 位置放的是 a，1位置放的是 b，2位置放的是 c，因为数组本身就是一个索引表；但是如果仅提供数组，无法知道 a 是放在哪个位置，b是放在哪个位置的，这就是因为没有反向索引表。即 arr[0] = a 是正向索引表，而 map[a] = 0 是反向索引表。

假设一开始 a = 5，b = 7，c = 9，那么很容易知道它们各自在堆的什么位置，但是如果 b 变成了 3，它需要往上移动，但是并不知道 b 在什么位置，只能遍历找到 b 的位置，然后看是否能调整，这个过程的时间复杂度是 O ( N ) O(N) O(N)；但是如果有反向索引表，就可以查到 b 在什么位置，从该位置直接向上调，是 O ( l o g N ) O(logN) O(logN) 的代价，而系统是没有反向索引表的，所以只能手写。

  在工程上，不同语言的应用场景可能不同，Java 多是应用，而C++ 中可能委员会提供了这样的反向索引表，但是也不在原生包中。可能设计Java 语言的人调研了堆的使用场景，最多也就是插入数据和取出数据，就没有增加反向索引表的动力，而且如果添加反向索引表还费内存。

public class HeapGreater {

	private ArrayList heap; //数组  //如果基础类型：ArrayList>，
	private HashMap indexMap; //反向索引表，假设原数组是[a, b, c], 那么反向索引表就记录的是a->0，b->1, c->2  //HashMap, Integer> 以避免不能放重复的数值
	private int heapSize; //堆的大小
	private Comparator comp; //比较器

	public HeapGreater(Comparator c) {
		heap = new ArrayList<>();
		indexMap = new HashMap<>();
		heapSize = 0;
		comp = c;
	}

	public boolean isEmpty() {
		return heapSize == 0;
	}c

	public int size() {
		return heapSize;
	}

	public boolean contains(T obj) {
		return indexMap.containsKey(obj);
	}

	public T peek() {
		return heap.get(0);
	}

	public void push(T obj) {
		heap.add(obj);
		indexMap.put(obj, heapSize);iff
		heapInsert(heapSize++);
	}

	public T pop() {
		T ans = heap.get(0);
		swap(0, heapSize - 1);
		indexMap.remove(ans);
		heap.remove(--heapSize);
		heapify(0);
		return ans;
	}

	public void remove(T obj) {
		T replace = heap.get(heapSize - 1);
		int index = indexMap.get(obj);
		indexMap.remove(obj);
		heap.remove(--heapSize);
		if (obj != replace) {
			heap.set(index, replace);
			indexMap.put(replace, index);
			resign(replace);
		}
	}

	public void resign(T obj) {
		heapInsert(indexMap.get(obj));
		heapify(indexMap.get(obj));
	}

	// 请返回堆上的所有元素
	public List getAllElements() {
		List ans = new ArrayList<>();
		for (T c : heap) {
			ans.add(c);
		}
		return ans;
	}

	private void heapInsert(int index) {
		while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
			swap(index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}

	private void heapify(int index) {
		int left = index * 2 + 1;
		while (left < heapSize) {
			int best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
			best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
			if (best == index) {
				break;
			}
			swap(best, index);
			index = best;
			left = index * 2 + 1;
		}
	}

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

其中的 T 一定要是非基础类型，因为反向索引表 indexMap 中的 key 如果是个基础类型，那么重复的数值就不能存放了。
所以如果是基础类型，就需要再包一层：

//如果是基础类型，就添加这个类
public static class Inner {
   	T value;
    Inner(T v) {
        value  = v;
    }
}

//HeapGreater 中的变量的定义同步修改为如下：
public class HeapGreater {

	private ArrayList> heap; //数组
	private HashMap, Integer> indexMap; //反向索引表
	private int heapSize; //堆的大小
	private Comparator comp; //比较器
	
	.....
}

template 
class HeapGreater {
private:
    typedef function comparator; //function 可以存放函数对象
    vector heap;
    unordered_map indexMap; //反向索引表
    int heapSize;
    comparator comp;
public:
    HeapGreater(comparator c) {
        heapSize = 0;
        comp = c;
    }

    bool isEmpty() {
        return heapSize == 0;
    }

    int size() {
        return heapSize;
    }

    bool containsKey(T &obj) {
        //return indexMap.find(obj) != indexMap.end();
        return indexMap.count(obj);
    }

    T top() {
        return heap[0];
    }

    void heapInsert(int index) {
        while (comp(heap[index], heap[(index - 1) / 2])) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    void push(T &obj) {
        heap.push_back(obj);
        indexMap[obj] = heapSize;
        heapInsert(heapSize++);
    }

    T pop() {
        T ans = heap[0];
        swap(0, heapSize - 1);
        indexMap.erase(ans);
        heap.pop_back();
        --heapSize;
        heapify(0);
        return ans;
    }

    void remove(T &obj) {
        T replace = heap[heapSize - 1];
        int index = indexMap[obj];
        indexMap.erase(obj);
        heap.pop_back();
        --heapSize;
        if (obj != replace) { //两个对象比较大小，自定义类型必须重载该运算符
            heap[index] = replace;
            indexMap[replace] = index;
            resign(replace);
        }
    }

    void resign(T &obj) {
        heap[indexMap[obj]] = obj;
        heapInsert(indexMap[obj]);
        heapify(indexMap[obj]);
    }

    vector getAllElements() {
        vector ans;
        for (T c : heap) {
            ans.push_back(c);
        }
        return ans;
    }

    void heapify(int index) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int best = left + 1 < heapSize && comp(heap[left + 1], heap[left]) ? left + 1 : left;
            best = comp(heap[best], heap[index]) ? best : index;

            if (best == index)
                break;

            swap(best, index);
            index = best;
            left = index * 2 + 1;
        }
    }

    void swap(int i, int j) {
        T o1 = heap[i];
        T o2 = heap[j];
        heap[i] = o2;
        heap[j] = o1;
        indexMap[o2] = i;
        indexMap[o1] = j;
    }


    T get(int ind) {
        return heap[ind];
    }
};

加强堆中主要的几点：

1. 建立反向索引表
2. 建立比较器
3. 核心在于各种结构相互配合，这一点非常容易出错