Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Heap<T extends Comparable<T>> extends ArrayList<T> {
- public void insert(T elem) {
- this.add(elem);
- int idx = this.size() - 1;
- if(idx > 0 && this.compare(idx, (idx - 1) / 2)){
- Collections.swap(this, idx, (idx - 1) / 2);
- idx = (idx - 1) / 2;
- }
- }
- public void removeTop() {
- if(this.size() == 1) {
- this.remove(0);
- return;
- }
- this.set(0, this.remove(this.size() - 1));
- int here = 0;
- while(true) {
- int left = here * 2 + 1;
- int right = here * 2 + 2;
- if(left >= this.size()) break;
- int next = here;
- if(!this.compare(next, left)) {
- next = left;
- }
- if(right < this.size() && !this.compare(next, right)){
- next = right;
- }
- if(next == here) break;
- Collections.swap(this, next, here);
- here = next;
- }
- }
- private void swap(int idx1, int idx2) {
- T temp = this.get(idx1);
- this.set(idx1, this.get(idx2));
- this.set(idx2, temp);
- }
- private boolean compare(int idx1, int idx2) {
- return this.get(idx1).compareTo(this.get(idx2)) >= 0;
- }
- }
- Heap<Integer> heap = new Heap<Integer>(new SomekindofCompareFunction());
- class Heap<T> extends ArrayList<T> {
- private final Comparator<T> comparator;
- public Heap(Comparator<T> comparator) {
- this.comparator = comparator;
- }
- private boolean compare(int idx1, int idx2) {
- return comparator.compare(get(idx1), get(idx2)) >= 0;
- }
- }
- Heap<Integer> heap = new Heap<Integer>((a,b) -> a.compareTo(b));
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement