# binary Heap
- 최대, 최소값 찾기에 효율적
- complete binary tree : 마지막 레벨 제외하고 모두 채워짐
- array 로 구현하면 트리에 비해 swap 이 효율적
- 메모리 힙이랑 다르다
- max heap, min heap
- priority : parent >= child. 즉 루트노드가 최대 또는 최소값
- 검색이 느리다


## 배열로 구현
- 인덱스로 접근이 쉬워진다  = O(1)
- remove root = O(1)
- insert
- search = O(N)


## 트리로 구현
- 노드에 접근하기 =  O(log N)
- remove root = siftDown 해야하므로 O(log n)
- insert = siftUp 해야하므로 O(log n)
- search = O(n)
- peek = O(1)


## remove root
- root 노드와 마지막 노드를 스왑
- 마지막 노드로 간 root 노드를 지운다
- 새로운 루트 노드가 제자리를 찾을 때까지. Sift down 한다
- siftDown = O(log n)

## insert
- 마지막에 넣기
- 제자리 찾을 때까지 sift Up
- O(log n)


## remove 임의의 인덱스 노드
- 마지막 노드와 스왑
- 새로운 이 마지막 노드를 삭제한다
- 마지막 노드가 올라간 자리가 제자리를 찾을 때까지 sift up, sift down 둘다 한다
- O (log n)


## search
- O(n)
- 찾을때 priority 에 따라서 위로 가거나 아래로 가거나