Heap, Binary Heap   힙, 이진 힙

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()  :  힙에 저장된 자료의 개수 확인