Heap(힙) 에 대한 간단(명료) 정리!

 

안녕하세요.

 

거두절미하고 간단 정리! 바로 작성하겠습니다.

 

 

 

 

 

Heap(힙)

---

  - 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조.

 

  - 여러 개의 값들 중에서 최댓값과 최솟값을 빠르게 찾아내도록 만들어진 자료구조.

 

  - 힙 트리에서는 중복된 값을 허용한다.

 

  - 힙은 키와 값을 가지는 노드가 이루어진 트리이다.

 

  - 주로 배열을 사용하고, 배열의 첫 번째 인덱스 0은 사용하지 않는다.

 

  - 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. (루트 = 1, 왼쪽 자식 = 2, 오른쪽 = 3)

 

    - 왼쪽 자식 index : 2 * 부모 index

    - 오른쪽 자식 index : (2 * 부모 index) + 1

    - 부모 index : 자식 index / 2

 

 

  - Max heap(최대 힙) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리.

      ** 보통, 왼쪽 자식 노드의 값이 오른쪽 자식 노드의 값보다 크다.

      ** key(부모노드) >= key(자식노드)

 

  - Min heap(최소 힙) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리.

      ** 보통, 왼쪽 자식 노드의 값이 오른쪽 자식 노드의 값보다 작다.

      ** key(부모노드) <= key(자식노드)

 

 

** binary heap의 높이(height = n) : O(logn)

 

 

 

 

Heap(힙) 그림 설명

---

 

HEAP 설명. 출처 : 학교 수업 PPT 자료

 

 

  - 위는 MaxHeap의 트리 구조를 나타낸 것

  - 아래는 MaxHeap을 배열(Array)로 나타낸 것 (index 0은 사용하지 않음)

 

 

 

 

 

 

감사합니다.