11-2 히프 개념과 연산

1. 히프의 개념과 추상 자료형

① 히프의 개념

  - 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를

    찾기 위해서 만든 자료구조

  - 일반적으로 히프는 최대 히프를 의미

  - 같은 키 값의 노드가 중복되어 있을 수도 있음

2. 히프의 삽입, 삭제 연산

① 히프의 삽입 연산

  - 1단계 : 완전 이진 트리의 조건이 만족하도록 다음 자리 확장.

                (노드 n개인 완전 이진 트리에서 n+1자리 만들고 그자리에 삽입할 원소 임시 저장)

  - 2단계 : 부모노드 크기 조건이 만족하도록 삽입 원소의 위치 찾기

 

 

② 히프의 삭제 연산 : 히프에서는 루트 노드의 원소만 삭제 가능

  - 1단계 : 루트 노드의 원소를 삭제하여 반환

  - 2단계 : 원소의 개수가 n-1개로 줄었으므로 노드의 수가 n-1인 완전 이진 트리로 조정

  - 3단계 :  완전 이진 트리 내에서 루트에 임시 저장된 원소의 제자리 찾기

3. 순차 자료구조를 이용한 히프의 구현

①  히프의 구현

  - 1차원 배열의 순차 자료구조를 이용하면 인덱스 관계를 이용하여  부모노드 찾기 쉬움

② 히프 구조 :

  - 트리 구조 중에서 최대값/최솟값을 루트에 두고 정렬을 쉽게하고, 탐색을 쉽게 할 수 있는

    특별한 형태의 완전 이진 트리구조