Heap, Binary Heap   힙, 이진 힙

(2023-12-28)

1. 힙 (Heap) 

  ㅇ 피라미드 모양으로 쌓아 올린 더미 (돌 무더기)

  ㅇ [전산] 항상 제일 위에 있는 것을, 먼저 꺼내는 구조를 추상화시킨 것
     - [프로세스 관리, 메모리 관리]  
        . 프로그램 실행 중(런타임시)에, 
        . 작업 순서 또는 메모리 할당을, 동적으로 결정하는 관리 방식       ☞ 힙 메모리 참조
     - [자료구조 구현]  
        . 우선순위 큐를 구현하는 자료구조의 일종
           .. 우선순위 큐의 구현 방법 : 이진 힙, 피보나치 힙, 배열, 연결리스트 등을 이용


2. [전산]  이진 힙 (Binary Heap)

  ㅇ 특징
     - [형상]  완전 이진 트리
        . 각 레벨에 노드들이 꽉 차있는 이진 트리
        . 단, 마지막 레벨 제외 (왼쪽부터 채워지며, 오른쪽에는 비워질 수 있음)
     - [밀도]  완전 이진 트리이므로, 데이터 밀집성이 좋음 
        . 따라서, 배열로 구현하기 용이함
     - [정렬]  반 (느슨한) 정렬 상태를 유지
        . 부모,자식 간에는 대소 관계가 있으나, 형제들 간에는 대소 관계가 정해지지 않음
           .. 부모,자식 간에는, 키 값이 크거나 작아야 하지만, 
           .. 형제 간에는, 키 값의 크고작음이 무 상관
        . 이에따라, 부분 순서 트리 (Partial Ordered Tree) 라고도 함
        . 결국, 삭제 또는 삽입 연산 시 마다, 가장 큰/작은 값이 부모(루트)에 위치하게 됨 
     - [중복]  중복된 값 허용 가능

  ㅇ 이진 힙의 조건
     - 루트 값이 항상, 
        . 제일 크거(최대 힙)나 제일 작거(최소 힙)나 해야 함
     - 부모,자식 간 조건
        . 부모의 값이 자식 보다 항상 크다(최대 힙) 또는 항상 작다(최소 힙) 라는 조건을 만족 함
     - 형제 간 조건
        . 형제 간에는 값의 크고작음이 상관 없음
     - 마지막 레벨을 제외하고는, 각 레벨의 노드들이 모두 차 있음
        . 맨 아래 레벨에서는, 왼쪽부터 꽉 채워져 있음

  ㅇ 이진 힙의 종류
     - 최대 힙 (Max-Heap)  :  루트 노드가 가장 높은 값을 갖고, 각 노드의 값이 자식 값 보다 큼
     - 최소 힙 (Min-Heap)  :  루트 노드가 가장 낮은 값을 갖고, 각 노드의 값이 자식 값 보다 작음

  ㅇ 이진 힙의 구현
     - 통상, 배열로써 구현함 
        . 0번 인덱스 보다는 1번 인덱스부터 루트로써 시작됨
     - 특히, 완전 이진 트리 이므로, 메모리 낭비가 없게됨
     - 또한, 굳이 포인터도 필요 없게됨 
        . 인덱스에 대한 단순 계산으로 구분 가능함

  ㅇ 이진 힙의 노드 위치 (인덱스)
     - 부모 노드 위치는,  {# index(parent) = \left\lfloor index(child)/2 \right\rfloor #}
     - 왼쪽 자식 노드 위치는, {# index(leftChild) = index(parent) * 2 #} 
     - 로른쪽 자식 노드 위치는, {# index(rightChild) = index(parent) * 2 + 1 #} 

       

  ㅇ 응용  
     - 힙 정렬, 다익스트라 알고리즘 (최단 경로), 프림 알고리즘 (최소 신장 트리) 등
     * 여러 자료 중에, 가장 큰 값이나 가장 작은 값을, 빠르게 찾는데 유용


3. [전산]  이진 힙의 주요 연산 例)

  ㅇ push(e) 또는 insert(e)  :  요소 삽입
  ㅇ pop() 또는 poll()  :  루트로부터 값 읽어오며 삭제  
  ㅇ peek()  :  루트로부터 값 만 읽어오기
  ㅇ remove()  :  루트 또는 특정 요소 삭제
  ㅇ isEmpty()  :  힙이 비어있는지 확인
  ㅇ isFull()  :  힙이 가득차있는지 확인
  ㅇ size()  :  힙에 저장된 자료의 개수 확인

트리
   1. 트리   2. 트리 용어   3. 트리 종류   4. 트리 순회   5. 스패닝 트리   6. 이진 트리   7. 이진 트리 종류   8. 이진 탐색 트리   9. B 트리 (균형 트리)   10. 이진 힙   11. 멀티캐스트 트리   12. 결정 트리  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"