[자료구조]CH7. 트리(히프)

참조 : C로 배우는 쉬운 자료구조(이지영 저)

공부 날짜 : 21.02.22

 

<Section7> 히프의 개념과 연산 및 구현

 

1. 히프의 개념

 

 히프(Heap)는 완전 이진 트리에 있느 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기위해 만든 자료구조이다. 키값이 가장 큰 노드를 찾기 위한 히프가 최대 히프, 키값이 가장 작은 노드를 찾기 위한 히프가 최소 히프이다.

 

최대 히프는 {부모 노드의 키값>=자식 노드의 키값} 의 관계를 가지는 노드들의 완전 이진 트리이고,

최소 히프는 {부모 노드의 키값<=자식 노드의 키값} 의 관계를 가지는 노드들의 완전 이진 트리이다.

 

보통 일반적으로 히프라고 하면 최대 히프를 말한다.

 

2. 히프의 삽입 연산

 

 insertHeap(heap , item)

       if (n=heapSize) then heapFull();

       n←n+1; //현재 히프의 크기를 하나 증가 시켜서 노드 위치 확장

       for (i←n; ; ) do {

            if (i=1) then exit; // 원소가 이제 하나 들어간 것이므로 for문 탈출

            if (item <= heap[i/2] then exit; // 부모 노드가 item보다 값이 크면 삽입 위치 그대로 확정

            heap[i] ← heap[i/2]; //부모 노드의 값을 임시 자리에 저장한다.

            i ← (i/2); // 임시 삽입 위치를 부모 노드의 위치로 바꾸어 주고 다시 for문이 반복된다.

       }

       heap[i] ← item; // 삽입할 위치가 확정이 되면 그 자리에 item을 저장해 준다.

 end insertHeap()

 

3. 히프의 삭제 연산

 

 루트 노드가 삭제가 된다.

 

 deleteHeap(heap)

        if (n=0) then return error; // 공백이므로 삭제할 노드가 없음

        item ← heap[1]; // 루트 노드를 item에 저장

        temp ← heap[n]; //마지막 노드를 temp에 저장

        n ← n-1;

        i ← 1;

        j ← 2;

        while (j <= n) do {

           if (j < n) then 

                if (heap[j] <heap[j+1]) then j ← j+1; // 왼쪽 자식 노드, 오른쪽 자식 노드 중 큰 값을 고름

           if (temp >= heap[j]) then exit; // temp가 그 자식 노드 값 보다 크면 자리 확정하여 while문 탈출

           heap[i] ←heap[j]; // 자식 노드 값이 더 크면 부모 노드 위치에 자식 노드 값을 저장

           i← j; // 위치가 한 레벨 내려옴

           j←j*2; //그 위치에서의 자식 레벨을 다시 탐색

        }

       heap[i] ← temp; // 확정된 자리에 temp 저장

       return item;

 end deleteHeap()