Heap, Binary Heap   힙, 이진 힙

(2022-01-16)
1. 힙 (Heap) 

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

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


2. 이진 힙 (Binary Heap)포화 이진 트리의 일종
     - 부모,자식 간에는 대소 관계가 있으나, 형제들 간에는 대소 관계가 정해지지 않음
     - 이에따라, 부분 순서 트리(Partial Ordered Tree) 라고도 함

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

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

  ㅇ 이진 힙의 구현
     - 통상, 배열로써 구현함 (포화 이진 트리이므로 메모리 낭비가 없음)

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

  ㅇ 응용 : 힙 정렬

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


[트리] 1. 트리 2. 트리 용어 3. 트리 종류 4. 이진 트리 5. 이진 탐색 트리 6. 스패닝 트리 7. 트리 순회 8. B 트리 9. 10. 멀티캐스트 트리 11. 결정 트리
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   전기전자공학
  5.   방송/멀티미디어/정보이론
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
            1. 자료구조
            2. 자료구조 종류
        1.   선형 자료구조 (리스트 등)
        2.   비선형 자료구조 (그래프,트리)
          1.   그래프
          2.   트리
            1.   1. 트리
                2. 트리 용어
                3. 트리 종류
                4. 이진 트리
                5. 이진 탐색 트리
                6. 스패닝 트리
                7. 트리 순회
                8. B 트리
                9.
                10. 멀티캐스트 트리
                11. 결정 트리
        3.   기타 자료구조
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     요약목록     참고문헌