힙(Heap)
- 특정한 조건을 갖춘 이진트리
- 특정한 조건이란?
1) root 노드가 언제나 전체 트리 중 최댓값(max heap) 혹은 최솟값(min heap)
-> 자신의 서브트리 (왼쪽이건 오른쪽이건)보다 무조건 크거나(max heap), 무조건 작다 (min heap) -> 재귀적정의
2) 완전 이진 트리 -> 0~level-1 까진 포화, level 번째 에선 포화는 아니더라도 왼쪽부터 순차적으로 데이터가 있음
3) 오른쪽 서브트리와 왼쪽 서브트리 사이의 순서는 정의되지 않았다.
- 이진 탐색 트리와 달리 완전 이진 트리이지만, 노드의 자식 사이의 배치가 정해진 바 없어 이진 탐색 트리처럼 검색 기능을 제공하지 않는다.
- 순회도 제공하지 않는다.
[ Max Heap의 추상적 자료구조 ]
1) __init__(): 초기화
2) insert(item):새 원소 삽입
3) remove() - 최대 원소 (root node) 반환, 삭제
[ 데이터 표현의 설계 ]
- 배열을 사용해 힙을 설계하며, 위에서 아래로, 왼쪽에서 오른쪽으로 노드에 번호를 매긴다.
- 그 번호가 배열에 노드가 저장될 인덱스가 된다.
- root 노드를 1로 뒀을 때 m번 노드가 있을 때,
왼쪽 자식은 2*m
오른쪽 자식은 2*m+1
부모 노드는 m//2
- '완전 이진 트리' 조건에 맞게 추가와 삭제는 마지막 노드, 처음 노드에서만 이루어진다.
=>이진 탐색 트리처럼 lookup & remove가 의미 없는 이유
[ 코드 구현 ]
힙 초기화
class MaxHeap:
def __init__(self):
self.data = [None]
[ 최대 힙에 원소 삽입 ]
1. 트리의 마지막 자리에 새로운 원소를 임시로 저장한다.
2. 부모>자식 룰을 지키기 위한 작업 - 부모 노드와 키 값을 비교하여, 부모가 추가된 노드보다 작을 경우 바꾸면서 위로 이동한다.
원소 삽입의 복잡도는 O(logN)인데, 부모노드로 올라가면서 인덱스 번호가 반으로 줄어들기 때문이다.
insert() 메소드
class MaxHeap:
##초기화 ##
def insert(self, item):
#우선 맨 끝자리에 넣기
self.data.append(item)
#인덱스 초기화
i = self.data.index(item)
while i>1 and self.data[i]>self.data[i//2] :
#조건 순서 유의 - data[0]을 비교하는 일이 없도록 i>1 을 먼저 추가.
self.data[i],self.data[i//2] = self.data[i//2],self.data[i]
i//=2
#자리에 넣기
[ 최대 힙에서 원소 삭제]
- 아래에서 위로 올라가던 원소 추가와 반대로 위에서 아래로 내려가면서 진행한다.
1. 원소를 삭제할 땐 최대 값을 뽑는 개념으로, 처음 루트 노드만 제거 가능하다.
2. 하지만 완전 이진 트리의 형식을 유지해야 하기 때문에, 트리 마지막 배열 칸(원소가 삭제되면 쓸모 없어 지므로) 루토 노드의 자리에 배치한다. => 완전 이진 트리의 '모양'은 유지한 상태로 루트 노드가 빠져나가게 된다.
3. BUT, 항상 자식 서브 트리보다 값이 커야한다는 최대 힙의 규율에 어긋나므로 루트에 배치된 원소(원래 맨 마지막 칸에 있었음) 자식과 비교하여 아래로 이동하며 알맞은 위치로 놓아야 한다.
-> 두 자식 중 큰 값과 비교한다. (부모 > 왼쪽, 오른쪽 자식 이므로 본인, 왼쪽, 오른 쪽 중 가장 큰 것이 부모의 위치에 와야 하기 때문)
원소 삭제의 시간복잡도는 O(logN)인데, 실제 비교 횟수는 2*logN이며 여기서 상수를 제외한 것이다.
이는 아래로, 아래로 내려가면서 범위가 반으로 줄어들기 때문에 logN, 왼쪽, 오른쪽 자식 중 큰 것을 찾는 과정이 추가되어 비교횟수가 2배가 되었기 때문이다.
remove() 메소드
class MaxHeap:
##다른 메소드##
def remove(self): #key안받고 root 노드만 삭제
if len(self.data)>1:
#우선 맨 끝자리 (곧 삭제되서 쓸모 없게 될 자리)와 루트 교환
self.data[1],self.data[-1] = self.data[-1],self.data[1]
data = self.data.pop(-1) #크기 1 줄어듦
self.maxHeapify(1) #1번 부터 시작에서 트리의 규율 유지해주도록 재정렬
else:#아예 루트 노드를 지움, 자리를 바꿔서 비교할 것들이 없음
data = None
return data
def maxHeapify(self,i):
#오른쪽 child, 왼쪽 child 인덱스 계산
left = 2*i
right = 2*i+1
#가장 큰 것의 인덱스에 본인 저장 (temp)
smallest = i
#자기 자신, 왼쪽, 오른쪽 자식 중 최대치를 찾는다 - 만약 smallest와 다르다면, 자식중 하나가 본인보다 크고, 자리를 바꿔야한다.
##이 때 자식이 있는지 없는지 범위를 검사해준다.
##종료 조건 1: child가 없을때 종료(완전 이진트리이므로 범위 초과시)
if left<len(self.data) and self.data[left]>self.data[smallest]:
smallest = left
if right<len(self.data) and self.data[right]>self.data[smallest]:
smallest = right
if smallest !=i:
#자리 이동이 필요한 경우-i와 smallest 변경
self.data[i],self.data[smallest] = self.data[smallest],self.data[i]
#재귀적으로 maxHeapify 호출
self.maxHeapify(smallest)
#종료 조건2: 자기 자신이 최대라면 더이상 이동할 필요 없음
[ 최대 / 최소 힙의 응용 ]
1. 우선순위 큐
- Enqueue 할때 '느슨한 정렬'을 유지하도록 한다 - 느슨한 정렬이란, 배열로 이루어진 모든 큐가 다 순서대로 정렬된 것은 아니지만, 즉 힙에서 자식 사이의 대소는 보장할 수 없지만, 부모 > 자식은 보장된 정렬
시간 복잡도는 O(logN) 이다 (insert 메소드의 시간복잡도)
- Dequeue할 때 순서대로 추출 - O(logN)
- 기존에 양방향 리스트로 구현할 땐, (만약 정렬된 상태로 enqueue하고자 할 경우)원소들을 하나하나 비교해봐야 해서 Enqueue할 땐 O(N), Dequeue할 땐 O(1)의 시간복잡도가 소요됐다. 이 경우 추가할 땐 힙이, 삭제할 땐 연결리스트가 더 효율적이다.
2. 힙 정렬
- 정렬되지 않은 원소를 아무 순서로 힙에 삽입한다 (O(logN)) -> 힙 내엔 정렬된 상태로 존재한다.
- 삽입이 끝나면, 힙이 빌 때까지 힙의 원소를 삭제하며 루트를 하나씩 추출한다 (O(logN))
- 이 과정을 전체적으로 표현하면, O(N*logN (모든 원소 삽입) + N*logN(모든 원소 추출))이며 이는 즉 O(NlogN)이 된다.
- 힙 정렬을 코드로 구현하기 위해선, 다음과 같은 과정을 따른다.
1. 리스트에 저장된 원소들을 하나씩 Heap 에 insert()한다.
2. 모든 원소를 insert한 후, Heap 에 저장된 원소들을 하나씩 remove하여 새로운 배열에 저장한다.
3. 모든 원소의 remove가 끝나면 정렬된 원소가 모두 저장된 배열을 반환한다.