[Data Structure] Heap

이 포스팅은 세미나를 위해 
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다.

Heap

• 완전 이진 트리(Complete Binary Tree) 기반 자료구조로 반정렬 상태(느슨한 정렬 상태)를 유지한다.
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
  • 형제 또는 사촌 노드 간의 우선순위는 정해진 것이 없음
• 힙은 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않음)
• 종류
  • 최대 힙(Max Heap)
    • key(부모 노드) ≥ key(자식 노드)
  • 최소 힙(Min Heap)
    • key(부모 노드) ≤ key(자식 노드)
• 시간 복잡도
  • Max(Min) Heap에서 최대(최소) 값을 찾는 데 걸리는 시간 복잡도는 O(1)이다. (루트 노드가 최대(최소) 값이기 때문) 또한, Complemete Binary Tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다. (random access 가능)
  • 하지만 heap의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다. 대체 방법으로 마지막 노드(제일 마지막 index의 노드)를 루트 노드로 대체한 뒤, heapify 과정을 거쳐 heap 구조를 유지한다. heapify 과정이 필요하기 때문에 결국엔 O(log n)의 시간 복잡도로 최대(최소) 값에 접근할 수 있다.

출처: https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

힙 정렬(Heap Sort)

• 힙에서 자료를 꺼낼 때 가장 큰(작은) 값부터 나오는 성질을 이용한 정렬
• 시간 복잡도: O(n * log n)

---

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html