Heap, Binary Heap   힙, 이진 힙

1. 힙 (Heap) 

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

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


2. 이진 힙 (Binary Heap)

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

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

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

  ㅇ 이진 힙의 구현
     - 통상, 배열로써 구현함 
     - 특히, 완전 이진 트리 이므로, 메모리 낭비가 없게됨
     - 또한, 굳이 포인터도 필요 없게됨 (인덱스에 대한 단순 계산으로 구분 가능하므로)
       

  ㅇ 이진 힙의 노드 위치 (인덱스)
     - 왼쪽 자식 노드 위치를 i라고 하면, 오른쪽 자식 노드 위치는 i+1, 부모 노드 위치는 i/2 

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

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


3. 피보나치 힙

  ㅇ ... (편집중) ...