[Data Structure] Heap

🙋‍♀️Heap

• 완전 이진 트리의 일종
  • 삽입 시, 왼쪽에서부터 삽입하게 된다.

• 삽입/삭제 시간복잡도: O(logn)

• 힙의 경우, 중복된 값을 허용한다.

🙋‍♀️종류

• 최대 힙(max heap)
  • 부모노드의 key >= 자식노드의 key

• 최소 힙(min heap)
  • 부모노드의 key <= 자식노드의 key

• 부모노드와 자식노드의 관계
  • 왼쪽 자식의 index = 부모 index * 2
  • 오른쪽 자식의 index = 부모 index * 2 + 1
  • 부모 index = 자식 index // 2
• 힙을 저장하는 표준적인 자료구조 = 배열

🙋‍♀️최대 힙: 삽입

• 최대 힙, 최소 힙의 삽입/삭제 과정은 유사하므로 최대 힙의 삽입/삭제의 과정만을 살펴보겠다.

• 배열의 끝에 새로운 값을 삽입한다.

• 부모 노드의 값과 비교하여 부모 노드의 값보다 큰 값일 경우 서로 교환한다.

• 배열의 시작까지 다다르거나, 부모노드보다 값이 작을 경우까지 위 과정을 반복한다.

🙋‍♀️ 최대 힙: 삭제

📃참고

• https://juhee-maeng.tistory.com/94
• https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html