heap 기초개념 및 구현실습 - 양태환 강사님 강의
.
그림, 실습코드 등 학습자료 출처 :
1) https://github.com/ythwork
2) https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
1. heap 개요
-
힙은 완전이진트리의 일종으로 우선순위 큐 구현을 위해 만들어진 자료구조이다.
-
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어졌다.
-
힙은 일종의 ‘반정렬 상태’를 유지한다.
간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
- 힙 트리에서는 중복된 값을 허용한다.
이진 탐색 트리에서는 중복된 값을 허용하지 않는다.
2. 우선순위 큐
큐긴 큐인데 선입선출이 아니라 데이터에 우선순위를 정해서 우선순위가 높은 순위가 먼저 out될 수 있도록 하는 큐이다.
ex) 잡 스케쥴링, 자바스크립트 이벤트 구현 등
- 우선순위 큐 ADT
1) pq.push(elem) : 우선순위를 가진 원소를 삽입하면 자동으로 재정렬
2) pq.pop() : 우선순위가 가장 큰 원소를 삭제 후 반환
3) pq.top() : 우선순위가 가장 큰 원소를 삭제하지 않고 반환
3. 힙의 종류
4. 최대 힙 예시
- 부모 인덱스를 구하는 방법
공식 : 부모인덱스 = 인덱스 / 2
ex) 2번 인덱스의 부모 : 1, 5번 인덱스의 부모 : 2
- 자식 인덱스를 구하는 방법
공식 : 왼쪽 자식인덱스 : 인덱스 * 2, 오른쪽 자식인덱스 : 인덱스*2 + 1
ex) 2번 인덱스의 왼쪽자식 : 4, 2번 인덱스의 부모 : 5
5. 최대 힙에서 push
step1) 새로운 원소를 완전 이진트리 유지를 위해 가장 아래의 왼쪽에 삽입한다.
step2) 삽입된 원소와 그것의 부모 key와 비교해서 삽입된 원소가 부모보다 크면 서로 데이터를 바꿔주는 것을 반복한다. 부모의 키가 더 크면 종료한다.
while문으로 구현시 temp의 key가 parent of key보다 크면 바꿔주는 알고리즘
5. 최대 힙에서 pop
step1) 루트가 가장크기 때문에 루트를 뽑아주면 된다.
step2) 루트가 공석이기 때문에 채워줘야 한다. 완전이진트리를 유지하기 위해서는 가장 아래의 오른쪽을 루트로 옮겨주면된다.
step3) 가장 큰 데이터가 루트에 와야 하는데 그게 아니므로 현재 루트의 자식노드 중 큰 자식노드와 비교해서 바꿔준다.
step4) 또 그 자식과 큰 놈과 또 비교해서 현재 temp가 더 작으면 교환하고 하니면 종료한다.
6. 최대 힙 파이썬 코드구현
class Element: ## 키와 데이터를 가리키는
def __init__(self, key, data=None):
self.key = key
self.data = None
class MaxHeap:
## 힙을 구현하는 내부 자료구조는 배열(list 또는 array)이다.
MAX_ELEMENTS=200 ## 데이터를 200개까지 저장하는 한도를 정해줌
def __init__(self):
self.arr = [None for i in range(self.MAX_ELEMENTS)]
self.heapsize = 0
def is_empty(self):
if self.heapsize==0:
return True
return False
def is_full(self):
if self.heapsize>=self.MAX_ELEMENTS:
return True
return False
def __get_parent_idx(self, idx): ## idx는 키값은 아니다.
return idx // 2
## 부모의 인덱스를 계산해서 리턴
def __get_left_child_idx(self, idx):
return idx * 2
def __get_right_child_idx(self, idx):
return idx * 2 + 1
def push(self, item):
if self.is_full():
raise IndexError("the heap is full!!")
self.heapsize+=1
cur_idx=self.heapsize
#cur_idx가 루트가 아니고
#item의 key가 cur_idx 부모의 키보다 크면
while cur_idx! = 1 and item.key > self.arr[self.__get_parent_idx(cur_idx)].key :
self.arr[cur_idx] = self.arr[self.__get_parent_idx(cur_idx)]
cur_idx = self.__get_parent_idx(cur_idx)
self.arr[cur_idx] = item
def __get_bigger_child_idx(self, idx):
## pop함수에서 '두 자식 원소중 key가 더 큰 원소를 선택'할때 쓰는 함수
if self.heapsize < self.__get_left_child_idx(idx):
return None
## case1) self.heapsize < self.__get_left_child_idx(idx) 경우
## idx는 leaf 노드다
elif self.heapsize == self.__get_left_child_idx(idx):
return self.__get_left_child_idx(idx)
## case2) self.heapsize == self.__get_left_child_idx(idx) 경우
## idx의 자식이 왼쪽노드 하나가 있다.
else:
## case3) self.heapsize > self.__get_left_child_idx(idx) 경우
## idx 자식이 왼쪽 오른쪽 둘다 있는 경우
## 이 경우에는 왼쪽 오른쪽 자식을 비교해서 더 큰것을 반환한다.
## 반환하는 것은 엘리먼트를 반환하는 것이 아니라 인덱스를 반환한다.
left_child = self.__get_left_child_idx(idx)
right_child = self.__get_right_child_idx(idx)
if self.arr[left_child].key > self.arr[right_child].key:
return left_child
else:
return right_child
def pop(self):
if self.is_empty():
return None
#삭제된 후 반환될 원소
rem_elem = self.arr[1]
#맨 마지막에 위치한 원소
temp = self.arr[self.heapsize]
## 아래코드들은 루트에서 시작, 아래로 쭉 이어짐
cur_idx = 1
## 루트 인덱스를 의미함
bigger_child_idx = self.__get_bigger_child_idx(cur_idx)
## 현재 위치에서 bigger_child_idx는 루트의 좌측 차일드 인덱스
while bigger_child_idx and temp.key < self.arr[bigger_child_idx].key:
self.arr[cur_idx] = self.arr[bigger_child_idx]
cur_idx = bigger_child_idx
bigger_child_idx = self.__get_bigger_child_idx(cur_idx)
self.arr[cur_idx] = temp
## 힙에서 가장 마지막 원소
self.heapsize -= 1
return rem_elem
def top(self):
if self.is_empty():
return None
return self.arr[1]
def print_heap(h):
for i in range(1, h.heapsize+1):
print("{}".format(h.arr[i].key), end=" ")
print()
- push
h=MaxHeap()
e=Element(2)
h.push(e)
e=Element(14)
h.push(e)
e=Element(9)
h.push(e)
print_heap(h)
14 2 9
e=Element(11)
h.push(e)
print_heap(h)
14 11 9 2
e=Element(6)
h.push(e)
e=Element(8)
h.push(e)
print_heap(h)
14 11 9 2 6 8
- pop
rem=h.pop()
print("poped item is {}".format(rem.key))
print_heap(h)
rem=h.pop()
print("poped item is {}".format(rem.key))
print_heap(h)
rem=h.pop()
print("poped item is {}".format(rem.key))
print_heap(h)
rem=h.pop()
print("poped item is {}".format(rem.key))
print_heap(h)
rem=h.pop()
print("poped item is {}".format(rem.key))
print_heap(h)
rem=h.pop()
print("poped item is {}".format(rem.key))
print_heap(h)
poped item is 14
11 8 9 2 6
poped item is 11
9 8 6 2
poped item is 9
8 2 6
poped item is 8
6 2
poped item is 6
2
poped item is 2