-
최대 힙 - BasicC 자료구조/Heap 2020. 6. 28. 00:59
들어가기에 앞서, 책 <C언어로 쉽게 풀어쓴 자료구조>와 <윤성우의 열형 자료 구조> 인용
1. 힙의 개념
힙은 여러 개의 값들 중에서
가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다.
히프 트리에서는 중복된 값을 허용한다.
(이진 탐색 트리에서는 중복된 값을 허용하지 않았다.)
힙의 목적은 삭제 연산이 수행될 때마다
가장 큰 값 혹은 가장 작은값을 찾아내기만 하면 되는 것이다.
힙은 2가지가 있다.
부모 노드의 키값이 자식노드의 키값 보다 큰 최대 힙
반대로 부모 노드의 키값이 자식 노드의 키값 보다 작은 최소 힙이 있다.
(위의 2가지 힙은 단지 부등호만 달라지고 나머지는 완전히 동일하다.)
힙은 완전 이진 트리이다. 여기서는 구현의 방식은 최대 힙으로 할 것이다.
값이 곧, 우선 순위이다. 값이 클수록 우선 순위는 높다.
[아래의 그림이 최대 힙]
[아래의 그림이 최소 힙]
2. 최대 힙의 구현 방식
힙은 완전 이진 트리 이기 때문에 아래의 [그림 1]처럼 차례대로 번호를 붙일 수 있다.
( 노드 위의 초록색 숫자가 번호 )
이 번호를 배열의 인덱스로 생각하면 배열에 힙의 노드들을 저장할 수 있다.
따라서, 힙을 저장하는 표준적인 자료 구조는 배열이다.
구현의 용이함을 위해서, 배열의 첫번째 인덱스인 0은 사용하지 않는다.
[그림 1]
특정 위치의 노드번호는 새로운 노드가 추가되어도 변하지 않는다.
가령, 루트노드의 오른쪽 노드의 번호는 항상 3번이다.
배열을 이용하여 힙을 저장하면,
완전 이진 트리에서처럼 자식 노드와 부모 노드를 쉽게 알 수 있다.
위의 그림의 3번 노드를 가지고 3번 노드의 왼쪽 자식과 오른쪽 자식을 구해보자.
3. 힙의 삽입
히프에 새로운 요소가 들어오면, 일단 새로운 노드를 히프의 마지막 노드에 이어서
삽입 된다.
마지막 노드 다음에 새로운 노드를 위치시키면 히프 트리의 성질이 만족되지 않을 수 있다.
따라서, 삽입 후에 새로운 노드를, 부모 노드들과 교환해서 히프의 성질을 만족시켜
주어야 한다.
삽입 연산은 아래의 그림을 통해서 히프를 재구성한다.
위의 [그림 1]의 최대 히프에 8을 삽입한다고 가정하자.
step 1) 먼저, 번호순으로 가장 마지막 위치에 이어서 새로운 요소 8이 삽입된다.
step 2) 부모 노드4와 비교하여 삽입 노드8이 더 크므로, 교환한다. (아래그림은 교환 후 모습)
step 3) 부모 노드7과 비교하여 삽입 노드8이 더 크므로, 교환한다. (아래그림은 교환 후 모습)
step 4) 삽입 노드8이 부모 노드9보다 작으므로, 더 이상 교환하지 않는다.
힙 트리에서 삽입 알고리즘 (최대힙 기준)
힙 트리에서 삽입 알고리즘 의사코드(최대 힙 기준)
알고리즘 설명(최대힙 기준)
1. 히프 크기를 하나 증가시킨다.
3. 증가된 히프 크기 위치에 새로운 노드를 삽입한다.
4. i가 루트 노드가 아니고, i번째 노드가 i의 부모 보다 크면
5. i번째 노드와 부모 노드와 교환.
6. 한 레벨 위로 올라간다.
실제 구현에서는 교환이 아니라,
그냥 부모 노드만을 끌어내린 다음에 삽입될 위치가 확실해지면
새로운 노드는 그 위치로 이동한다.
이렇게 구현하는 편이 이동 횟수를 줄일 수 있다.
최소 힙을 만들고 싶다면 위의 while문에서 부등호의 방향을 바꾸어주기만 하면 끝.
아래는 위의 의사코드에서 부등호의 방향만 바꾸고 최소 힙을 구현할 수 있다.
4. 힙의 삭제
최대 히프에서 삭제 연산은 최대값을 가진 요소를 삭제하는 것이다.
최대 히프에서 최대값은 루트 노드이므로, 루트 노드가 삭제 된다.
삭제 후에, 히프를 재구성하는 것이 필요하게 된다.
히프의 재구성이란 히프의 성질을 만족하기 위하여 위, 아래 노드를 교환하는 것이다.
[그림 1]에서 루트 노드를 삭제한다고 가정해보자.
아래의 그림을 보자.
Step 1). 먼저 루트 노드가 삭제된다. 빈 자리에는 히프의 마지막 노드를 가져온다.
Step 2). 새로운 루트인 3과 자식 노드들을 비교해보면 자식 노드가 더 크기 때문에,
교환이 일어난다. 자식 중에서 더 큰 값과 교환이 일어난다. 따라서 3과 7이 교환 된다.
Step 3). 아직도 3이 자식 노드들보다 더 작기 때문에, 3과 자식 노드5를 교환한다.
Step 4). 3이 자식 노드인 2와 1보다 크기 때문에, 더 이상의 교환은 필요없다.
힙 트리에서의 삭제 알고리즘 의사코드
최대힙의 삭제 알고리즘 설명
1. 루트 노드 값의 반환을 위해서 item변수로 옮긴다.
2. 말단 노드를 루트 노드로 옮긴다.
3. 힙의 크기를 하나 줄인다.
4. 루트의 왼쪽 자식부터 비교를 시작한다.
5. i가 힙 트리의 크기보다 작으면 (즉, 힙 트리를 벗어나지 않았으면)
6. 오른쪽 자식이 더 크면
7 과 8. 두 개의 자식 노드 중에서 큰 값의 인덱스를 largest로 옮긴다.
9. largest의 부모 노드가 largest보다 크면
10. 중지
11. 그렇지 않으면 largest와 largest의 부모 노드를 교환한다.
12. 한 레벨 밑으로 내려간다.
13. 최대 값을 반환한다.
5. 메인 함수 및 힙의 초기화 함수 및 프로그램 실행 결과
6. 나머지 함수
헤더 파일 및 소스 파일