> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/heap.md).

# 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

```java
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)

```java
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)

```python
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
```