In [1]:
#22강 힙
'''힙이란?
1 루트 노드가 언제나 최대 또는 최소값을 가짐
-최대힙, 최소힙
2 완전 이진 트리여야함
최대힙(모든 노드가 부모가 자식보다 큼)
30
24 12
18 21 8 6
4 2 19
이진 탐색 트리와의 비교
1 원소들은 완전히 크기 순으로 정렬됐나? -> no
2 특정 키 값을 가지는 원소를 빠르게 검색하는가?->no
3 부가 제약 조건이 있는가? -> 완전 2진트리여야 함
최대 힙의 추상적 자료구조
연산의 정의
__init__()-빈 최대 힙을 생성
insert(item)-새로운 원소를 삽입
remove()-최대 원소(root)를 반환(동시에 이 노드 삭제)
데이터 표현의 설계
배열을 이용한 이진 트리의 표현
30 1
24 12 2 3
18 21 8 6 4 5 6 7
4 2 19 8 9 10
노드번호 m을 기준으로
왼쪽 자식의 번호: 2m
오른쪽 자식의 번호:2m+1
부모 노드의 번호 : m//2
완전 이진 트리이므로:노드의 추가/삭제는 마지막 노드에서만
배열로 표현(완전 이진트리(두개씩 있어)라 가능)
0 none
1 30
2 24
3 12
4 18
5 21
6 8
7 6
8 4
9 2
10 19
최대 힙에 원소 삽입- 복잡도
원소의 개수가 n인 최대 힙에 새로운 원소 삽입
-> 부모 노드와의 대소 비교 최대 회수 : log 2 n [O(log n)]
'''
#22강 실습: 최대 힙에 새로운 원소 삽입
class MaxHeap:
def __init__(self):
#0번 인덱스는 none
self.data = [None]
def insert(self, item):
#끝에서 부터 시작
curr=len(self.data)
#
self.data.append(item)
while curr>1:
if self.data[curr//2]<self.data[curr]:
self.data[curr],self.data[curr//2]=self.data[curr//2],self.data[curr]
curr=curr//2
def solution(x):
return 0
In [ ]:
#23강 힙
'''최대 힙의 원소의 삭제
1 루트 노드의 제거- 이것이 원소들 중 최대값
but 루트노드가 빈자리면 이진트리의 구조가 파괴됨
2 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
3 더큰 자식 값과 자리를 계속 바꿔감
-자식은 둘 있을 수도 있는데, 어느 쪽으로 이동?
20
6 12
2 4
루트노드 20 제거
그자리에 4 삽입
4
6 12
2
자식들과 크기 비교후 12와 바꿈
12
6 4
2
복잡도 : 원소의 개수가 n인 최대 힙에서 최대 원소 삭제
-> 자식 노드들과의 대소 비교 최대 회수 :2 log 2 n [O(logn)]
최대/최소 힙의 응용
1 우선 순위 큐
-enqueue 할 때 '느슨한 정렬'을 이루고 있도록함 :O(logn)
-Dequeue 할 때 최대값을 순서대로 추출 :O(logn)
2 힙 정렬
-정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 O(logn)
-삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제 O(logn)
-원소들이 삭제된 순서가 원소들의 정렬순서
-정렬 알고리즘의 복잡도 O(logn)
def heapsort(unsorted):
H=MaxHeap()
for item in unsorted:
H.insert(item)
sorted=[]
d=H.remove()
while d:
sorted.append(d)
d=H.remove()
return sorted
'''
#23강 실습: 최대 힙에서의 원소 삭제
class MaxHeap:
def __init__(self):
self.data = [None]
def remove(self):
if len(self.data) > 1:
self.data[1], self.data[-1] = self.data[-1], self.data[1]
data = self.data.pop(-1)
self.maxHeapify(1)
else:
data = None
return data
def maxHeapify(self, i):
# 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
left = 2*i
# 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
right = 2*i+1
smallest = i
# 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
if left < len(self.data) and self.data[left]>self.data[smallest]:
# 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
smallest=left
# 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
if right< len(self.data) and self.data[right]>self.data[smallest]:
# 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
smallest=right
if smallest != i:
# 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
self.data[i],self.data[smallest]=self.data[smallest],self.data[i]
# 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
self.maxHeapify(smallest)
def solution(x):
return 0
'탐색, 자료구조, 알고리즘' 카테고리의 다른 글
| 트리, 이진탐색 트리 실습 (1) | 2023.12.23 |
|---|---|
| (스택응용) 중위표현식 후위표현식 변환 (1) | 2023.12.23 |
| 큐, 환형큐 실습 (0) | 2023.10.18 |
| 연결리스트 정의와 실습 (0) | 2023.10.17 |
| 이진탐색, 재귀, 복잡도계산 (1) | 2023.10.16 |