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
Last updated
Was this helpful?