22강: 힙(Heaps) #1
힙(Heap)이란?
- 이진트리의 한 종류로서 이진 힙(binary heap)이라고도 부른다.
- 힙은 데이터 원소들의 순서를 교묘하게 표현한 트리로 데이터의 정렬에도 이용할 수 있다.
- 이를 이용한 데이터 정렬 알고리즘을 힙 정렬(heap sort)라고 부른다
힙의 종류
-
최대 힙과 최소 힙은 데이터 원소의 기준이 내림차순이나 오름차순이냐만 달라지고 완전히 대칭
- 최대 힙(max heap)
- 세 가지의 성질을 유지하고 있는 이진 트리
- 루트 노드가 항상 최댓값을 가진다
- 완전 이진 트리이다
- 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다(재귀적)
- 세 가지의 성질을 유지하고 있는 이진 트리
- 최소 힙(min heap)
- 최대 힙과 완전히 대칭
이진 탐색 트리(binary search tree)와 다른점
- 이진 탐색 트리에서는 원소들이 완전히 크기 순서대로 정렬되어 있다
- 중위 순회를 하면 데이터를 정렬된 순서로 뽑아낼 수 있다
- 루트 노드로부터 시작하여 특정 원소를 빠르게 검색할 수 있다
- 최대 힙은 완전히 크기 순서대로 정렬되어 있지는 않다
- 느슨한 정렬되어있는 구조
- 트리를 순회함으로써 데이터를 정렬할 수는 없다
- 탐색 연산을 제공할 수 없다
최대 힙의 장점?
- 부가의 제약 조건, 완전 이진 트리(complete binary tree)여야 한다는 제약 때문에 n개의 노드로 이루어진 최대 힙의 높이(깊이)는 log(n) + 1(에서 소수 부분은 버림)로 정해진다
- 이 성질 때문에 데이터의 원소의 삽입/삭제 연산의 실행 시간은 언제나 log(n)에 비례한다
- 따라서 어떤 최대 힙이 존재할 때, 이 힙으로부터 반복적으로 루트 노드를 삭제하면(서 데이터 원소들을 꺼내면) 루트 노드에 들어있는 키가 힙 내에서 최대임이 보장되어 있으므로 데이터를 내림차순으로 정렬할 수 있고, 이 정렬에 소요되는 시간 또한 log(n)에 비례한다
- 힙이 항상 완전 이진 트리라는 성질을 트리의 표현에 있어서도 이점을 제공한다
- 규칙에 따라 노드를에 번호를 매기면, 이 번호 순서로 이루어진 선형 배열에 트리를 표현할 수 있다.
- 또 완전 이진 트리이므로 노드의 추가와 삭제는 배열의 맨 마지막 원소에서만 일어난다
최대 힙의 추상적 자료구조
연산의 정의
__init__()- 빈 최대 힙을 생성insert(item)- 새로운 원소를 삽입remove()- 최대 원소(root node)를 반환 (그리고 동시에 이 노드를 삭제)
데이터 표현의 설계
-
배열을 이용한 이진 트리의 표현
- 노드 번호 m을 기준으로
- 왼쪽 자식의 번호 : 2 * m
- 오른쪽 자식의 번호 : 2 * m + 1
- 부모 노드의 번호 : m // 2
완전 이진 트리이므로 노드의 추가/삭제는마지막 노드에서만
1
array = ['',30,24,12,18,21,8,6,4,2,19]
코드의 구현
class MaxHeap:
def __init__(self):
self.data = [None]
최대 힙에 원소 삽입
- 트리의 마지막 자리에 새로운 원소를 임시로 저장
- 부모 노드와 키 값을 비교하여 위로, 위로 이동(부모와 값을 바꾸는 식으로)
복잡도
- 원소의 개수가 n인 최대 힙에 새로운 원소 삽입
- 부모 노드와의 대소 비교 최대 회수 : log2n
- 최악 복잡도
O(logn)의 삽입 연산
삽입 연산의 구현 - insert(item) 메서드
1
2
3
4
5
6
7
8
9
10
class MaxHeap:
def insert(self, item):
self.data.append(item)
i = len(self.data) - 1
while i != 1:
if self.data[i] > self.data[(i // 2)]:
self.data[i], self.data[(i // 2)] = self.data[(i // 2)], self.data[i]
i = i // 2
else:
break
본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.
