Advertisement
Guest User

Untitled

a guest
Jun 17th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.71 KB | None | 0 0
  1. class Heap<T extends Comparable<T>> extends ArrayList<T> {
  2.  
  3. public void insert(T elem) {
  4. this.add(elem);
  5. int idx = this.size() - 1;
  6. if(idx > 0 && this.compare(idx, (idx - 1) / 2)){
  7. Collections.swap(this, idx, (idx - 1) / 2);
  8. idx = (idx - 1) / 2;
  9. }
  10. }
  11. public void removeTop() {
  12. if(this.size() == 1) {
  13. this.remove(0);
  14. return;
  15. }
  16. this.set(0, this.remove(this.size() - 1));
  17. int here = 0;
  18. while(true) {
  19. int left = here * 2 + 1;
  20. int right = here * 2 + 2;
  21. if(left >= this.size()) break;
  22. int next = here;
  23. if(!this.compare(next, left)) {
  24. next = left;
  25. }
  26. if(right < this.size() && !this.compare(next, right)){
  27. next = right;
  28. }
  29. if(next == here) break;
  30. Collections.swap(this, next, here);
  31. here = next;
  32. }
  33. }
  34.  
  35. private void swap(int idx1, int idx2) {
  36. T temp = this.get(idx1);
  37. this.set(idx1, this.get(idx2));
  38. this.set(idx2, temp);
  39. }
  40.  
  41. private boolean compare(int idx1, int idx2) {
  42. return this.get(idx1).compareTo(this.get(idx2)) >= 0;
  43. }
  44. }
  45.  
  46. Heap<Integer> heap = new Heap<Integer>(new SomekindofCompareFunction());
  47.  
  48. class Heap<T> extends ArrayList<T> {
  49. private final Comparator<T> comparator;
  50.  
  51. public Heap(Comparator<T> comparator) {
  52. this.comparator = comparator;
  53. }
  54.  
  55. private boolean compare(int idx1, int idx2) {
  56. return comparator.compare(get(idx1), get(idx2)) >= 0;
  57. }
  58. }
  59.  
  60. Heap<Integer> heap = new Heap<Integer>((a,b) -> a.compareTo(b));
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement