7. Heap

• Insert and delete: O(logn)

• lookup: O(1)

• k largest elements, store in minHeap. If element > k, drop the smallest

PriorityQueue

• add

• poll: retrieve and remove head of the queue

• peek: retrieve but not remove the head of queue

Comparator: 指定comparator物件告知如何排序，改寫compare

• PriorityQueue

PriorityQueue heap = new PriorityQueue(k, new Comparator<String>()
  public int compare(String s1, String s2){});

Comparable:

物件本身繼承comparable，在class裡改寫compareTo. e.g. Arrays.sort(A), Collections.sort(C)

public static class Star implements Comparable<Star>{
   private double x, y, z;

   Star(double x, double y, double z){
       this.x = x;
       this.y = y;
       this.z = z;
   }

   public double distance(){
       return Math.sqrt(x*x + y*y + z*z);
   }

   @Override
   public int compareTo(Star rhs){
       return Double.compare(this.distance(), rhs.distance());
       // return Double.compare(rhs.distance(), this.distance()); // decreasing

   }
}

Python

• class 必須實作 def __lt__(self, other)

from queue import PriorityQueue

class ListNode:
    def __init__(self, x):
     self.val = x
     self.next = None
     
class Wrapper():
    def __init__(self, node):
        self.node = node
    def __lt__(self, other):
        return self.node.val < other.node.val