- [자료구조&알고리즘 | WEEK02] 힙(Heap) 자료구조, 힙 정렬(Heap Sort)2022년 11월 06일 22시 08분 10초에 업로드 된 글입니다.작성자: nickhealthy
힙(Haep) 이란?
힙(Heap)이란 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
힙은 '부모의 값이 자식의 값보다 <항상 크거나 | 항상 작거나>' 부모 - 자식 간 두 값의 대소 관계가 일정해야 한다. 또한 이 조건을 만족하는 완전 이진 트리이다.
참고: 힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다.💡트리란?
트리는 각 원소를 의미하는 노드(node)들이 연결된 계층 구조를 띈다.
1. 가장 윗 부분에 위치한 루트(root)는 부모가 없는 노드,
2. 노드의 상하 관계에는 부모 노드(parent node)와 자식 노드(child node)가 있다.
3. 그리고 부모가 같은 자식 간의 관계를 형제 노드(sibling node)라고 한다.
💡완전 이진 트리란?
완전 이진 트리란 트리의 한 종류로 완전 이진 상태라는 특징이 있다.
1. 여기서 '완전'은 부모는 왼쪽 자식부터 추가하여 모양을 유지하라는 뜻이고,
2. '이진'은 부모가 가질 수 있는 자식의 최대 개수는 2개라는 의미이다.
최대 힙, 최소 힙 / 부모 - 자식 간 두 값의 대소 관계가 일정해야함 힙을 사용하는 이유와 시간 복잡도
배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(n)의 시간복잡도를 가지게 된다.
1. 이에 반해, 배열에 데이터를 넣고, 힙을 만드는 과정의 시간 복잡도는 O(log n)2. 따라서 힙 정렬은 원소의 개수만큼 작업을 반복하므로 전체 정렬하는데 걸리는 시간 복잡도는 총 O(n log n)
우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다.힙과 이진 탐색 트리의 공통점과 차이점
- 공통점: 힙과 이진 탐색 트리는 모두 이진 트리 구조
- 차이점
- 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
- 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 크다.
- 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건이 없다.
- 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소 값 검색을 위한 자료구조로 이해하면 된다.
힙과 이진 탐색 트리의 공통점과 차이점 힙(Heap)의 동작 과정
힙에서 '최댓값은 루트에 위치한다'는 특징을 이용하여 정렬하는 알고리즘인데, 구체적으로 다음과 같은 작업을 반복한다.
- 힙에서 최댓값인 루트를 꺼낸다.
- 루트 이외의 부분을 힙으로 만든다.
힙에 데이터 삽입하기 - 기본 동작
힙은 완전 이진 트리로, 삽입할 노드는 왼쪽 최하단부 노드부터 채워지는 형태로 삽입한다.
힙에 데이터 삽입 과정 힙의 데이터 삭제하기(Max Heap의 예)
힙의 용도는 최댓값 또는 최솟값을 root 노드에 놓아서, 최댓값과 최솟값을 바로 꺼내어 쓸 수 있도록 하는 용도
- root노드를 꺼낸다.(최댓값/최솟값)
- 마지막 원소(가장 하단의 오른쪽에 위치한 원소)를 루트로 이동시킨다.
- 마지막 원소가 루트로 옮겨진 이후, 아래의 구조는 모두 힙 구조를 만족하고 있다.
- root에서 시작하여 자신보다 값이 큰 child node와 자리를 바꾸고, 아래쪽으로 내려가는 작업을 반복한다. child node의 값이 작거나 leaf의 위치에 도달하면 종료 (swap)
힙의 데이터 삭제 과정 힙의 관계
힙은 부모의 값이 자식의 값보다 <항상 크다 | 항상 작다> 조건을 충족한 '완전 이진 트리'라고 했다.
(왼쪽 자식을 먼저 추가하고, 부모가 가질 수 있는 최대 자식 원소는 2개)
따라서 아래의 사진을 보면 앞에서 정의한 내용을 충족한다.
힙의 관계 이러한 규칙과 순서로 구성하면 다음과 같은 관계가 성립된다.
원소[i]에서
* 부모: a[(i - 1) // 2]
* 왼쪽 자식: a[i * 2 + 1]
* 오른쪽 자식: a[i * 2 + 2]예를 들어 a[3]의 부모는 a[1]이고, 왼쪽 자식과 오른쪽 자식은 각각 a[7], a[8] 이다.
또 a[2]의 부모는 a[0]이고, 왼쪽 자식과 오른쪽 자식은 각각 a[5], a[6] 이다. 모두 위의 관계를 만족한다.트리로 인덱스를 구별할 때 위의 계층부터 순서대로 왼쪽 --> 오른쪽 순으로 인덱스를 부여해주면
조금 더 쉽게 해당 노드가 어떤 인덱스인지 구별할 수 있다.
더 알아보기
힙 정렬 알고리즘 알아보기
위에서 소개한 과정을 간단히 정리하면 다음과 같다.
여기에서 n값은 배열의 원소 수이고, i값은 배열의 마지막 인덱스이다.i 값을 n -1로 초기화
1. a[0]과 a[i]를 교환한다.
2. a[0], a[1], ... a[i - 1]을 힙으로 만든다.
3. i 값을 1씩 감소시켜 0이 되면 종료, 그렇지 않으면 2로 돌아간다.이 순서대로 힙 정렬을 수행한다.
이때 중요한 것은 배열의 처음 상태가 힙의 요구사항을 만족하지 않을 수도 있다는 점이다.
따라서 이 순서를 적용하기 전, 배열을 반드시 힙으로 만들어야 한다!배열을 힙으로 만들기 - 2022/11/09(수) 추가 작성
루트를 삭제한 힙을 재구성하려면 마지막 원소를 루트로 이동시켜서 알맞은 위치까지 아래로 옮겨야했다.
이 방법을 그대로 계층적인 서브트리에 적용해서 배열을 힙으로 구현할 수 있다.가장 최하단 계층의 서브트리부터 순차적으로 힙으로 만들면서, 루트 노드까지 힙으로 만드는 과정을 거쳐야 한다.
(가장 아랫 부분의 작은 서브트리부터 상향식으로 진행)
오늘 마침 코치님께서 문제를 내주셨다.
문제 내용은 주어진 배열에서 힙 정렬을 도식화 또는 배열이 어떻게 바뀌는지 책에 나와 있는 코드를 보고 작성 해보는 것이었는데
1단계인 힙을 만드는 과정,
2단계인 힙 정렬 과정을 정리하려고 한다.
나는 도식화 하는 것이 더 알아보기가 편해서 직접 그려가면서 힙을 만드는 과정과 힙 정렬을 익혔다.
주어진 배열은 [1, 2, 3, 4, 4, 5, 5, 6] 이다.
사실 문제에서 주어진 배열은 조금 순서가 다른데, 다른 방식의 배열로 한번 더 연습해 보았다.
아이패드로 그려봤는데.. 아직 사용이 익숙치 않아서 그림을 잘 못 그렸습니다 ㅠㅠ.
주어진 배열을 힙으로 만드는 과정 (MAX HEAP)
가장 최하단 계층의 서브트리를 힙으로 만든다.
부모 - 자식이 하나씩 밖에 없으므로 대소관계를 비교하여 값을 교환해주면 된다.
가장 최하단 계층의 서브트리 두 번째 서브트리를 힙으로 만드는 과정
이제 최하단 계층은 위에서 힙으로 만들었고, 그 위의 서브트리 계층을 힙으로 만들면 된다.
여기서도 동일하게 자식과 부모의 대소관계를 비교하여 힙으로 만들어주면 된다.
두 번째 서브트리를 힙으로 만드는 과정 세 번째 서브트리를 힙으로 만드는 과정
이제 같은 계층의 오른쪽 서브트리를 힙으로 완성 시켰으니,
왼쪽의 서브트리를 힙으로 만드는 과정이 필요하다.
이전에 첫 번째로 진행한(최하위 서브트리)까지 묶어서 힙으로 만드는 과정이 필요하다.
오른쪽 서브트리를 힙으로 만드는 과정처럼 부모 - 1촌 자식만(4,4) 힙으로 만들어줄 시, 리프노드('단말노드'라고도 함) '4'의 값이 맨 밑에 있게 되고, 이렇게 되면 힙의 부모-자식간의 대소관계가 깨지게 된다.
세 번째 서브트리를 힙으로 만드는 과정 네 번째 루트를 포함한 완전 이진 트리 전체를 힙으로 만드는 마지막 과정이다.
오른쪽의 사진처럼 루트 노드에는 최댓값인 '6'이 들어가게 되었고, 가장 아랫쪽엔 힙의 대소관계 조건을 통해 가장 작은 원소인 '1'이 리프노드에 들어가게 되었다.
이제 힙 정렬을 할 준비가 된 것 !!!
이렇게 만들어진 배열은 [6, 4, 5, 2, 4, 3, 5, 1] 이 될 것이다. (MAX HEAP 완성)
배열을 힙으로 만드는 과정을 완성한 모습 힙 정렬 과정(오름차순)
힙 정렬의 과정은
1. 루트 노드를 리프노드로 보낸다.(오름차순이 되야하니까) 이후, 정렬된 배열에 대해서는 다시 안봐도 됨
- 루트 노드가 최댓값이니까 루트 노드를 빼내서 n - 1의 배열에 넣어주면 된다.
- 다음 최댓값은 n - 2 배열에 넣음
2. 최하위의 원소를 루트 노드로 보낸다.
3. 배열을 힙 구조로 다시 만든다.
위의 과정을 반복
힙 정렬 과정은 아래의 사진과 같다.
배열에서 정렬된 원소에 대해서는 파란색을,
정렬된 원소가 트리에 위치하는 곳은 노란색을,
앞으로 남은 원소들은 배열에서는 검은색, 트리에서는 파란 숫자
전체 코드
def heap_sort(arr): def down_heap(arr, left, right): temp = arr[left] parent = left # 왼쪽 노드를 부모로 설정 while parent < (right + 1) // 2: # 힙으로 만드려는 범위를 넘어가는 지 검사 cl = parent * 2 + 1 # 왼쪽 자식이 들어갈 인덱스 cr = cl + 1 # 오른쪽 자식이 들어갈 인덱스 # 자식 노드 중 큰 값을 child에 담음 # 자식 노드의 균형이 맞는 경우 (left_child < right_child) if cr <= right and arr[cr] > arr[cl]: child = cr else: # 자식 노드의 균형이 안맞는 경우 (left_child > right_child) or 부모 - 자식 쌍 x child = cl if temp >= arr[child]: # 부모 노드가 자식 노드보다 큰 경우(힙 균형 상태 OK) break # 부모 노드가 자식 노드보다 작은 경우 arr[parent] = arr[child] # 자식 노드와 부모 노드 위치 swap parent = child # 새로운 부모 노드(인덱스) 설정 arr[parent] = temp n = len(arr) for i in range((n - 1) // 2, -1, -1): # 절반 위치부터 진행 down_heap(arr, i, n - 1) # 현재 ~ 마지막 인덱스 for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] down_heap(arr, 0, i - 1) heap_sort([1, 2, 4, 4, 3, 5, 5, 6])
Ref
이전글이 없습니다.댓글