알고리즘 스터디 발표 차례라.. 겸사겸사.. 발표용 자료 만들기...
+내가 나중에 찾아보기 편하도록 정리하는 힙 정렬 알고리즘 포스팅
1. Heap
✅ 자료구조
heap(힙)이란?
- 최대값 / 최소값을 빠르게 찾아내기에 유리한, 완전이진트리를 기본으로 한 자료구조
시간복잡도 비교
- 배열의 최대값, 최소값 찾기 = O(n)
- Heap에서 찾기 = O(logn)
- 다음과 같은 부모와 자식 간의 힙 속성을 만족함 (형제 사이에는 해당 X)
- 항상 부모가 자식보다 값이 크거나(최대 힙) / 항상 부모가 자식보다 값이 작음 (최소 힙)
- 자식 노드의 최대 개수는 힙의 종류마다 다름, 보통 대부분의 경우 자식 노드의 개수가 최대 2개인 이진 힙(Binary Heap)을 사용
- 힙 정렬 뿐만 아니라 우선순위 큐, 허프만 코드를 구현할 때도 쓰임
✅ 종류
1) 최대 힙 (Max-Heap)
- 항상 부모노드 값이 자식노드의 값보다 크거나 같다.
그림의 왼쪽과 같이, 부모들이 항상 더 큰 값을 가지므로 제일 위의 root 노드가 가장 큰 값을 갖게 된다.
2) 최소 힙 (Min-Heap)
- 항상 부모노드 값이 자식노드의 값보다 작다.
그림의 오른쪽과 같이, 부모들이 항상 더 작은 값을 가지므로, 제일 위의 root 노드가 가장 작은 값을 갖게 된다.
2. Heap Sort(힙 정렬)
✅ 과정
1-1. 데이터 삽입 (예시 : 최대 힙)
1) 제일 아래 왼쪽 노드부터 채워짐
2) 채워진 노드가 그 위치의 부모 노드보다 크면 부모 노드와 자리 바꿈
1-2. 데이터 삭제
1) 보통 root 노드부터 삭제
- 최대값, 최소값을 사용하기 위해 사용하는 자료구조다 보니)
2) root 노드 삭제 후, 가장 마지막에 추가한 노드를 root 노드 자리로 옮김
3) 새로운 root 노드가 아래의 자식 노드들보다 작으면, 자식 노드 중 큰 값의 노드와 자리를 바꿔줌
✅ 구현
- 일반적으로 배열로 구현
- 구현을 쉽게 하기 위해 루트 인덱스는 1이다.
- 왼쪽 자식 인덱스 = 부모 인덱스 * 2
- 오른쪽 자식 인덱스 = (부모 인덱스 * 2) + 1
- 부모 인덱스 = 자식 인덱스 / 2
- 위의 인덱스가 왜 저렇게 계산이 되는지 더 자세한 설명이 필요하다면?
> 관련 블로그 링크 연결 (하단 그림 출처)
- 트리와 배열의 인덱스 순서를 알 수 있는 그림 (빨간숫자가 인덱스)
⌨️ 코드
파이썬에서는 'heapq' 라는 내장함수를 사용한다.
-
힙 리스트 생성, 원소 추가
힙은 기본적으로 빈 리스트에서 시작해 힙 모듈로 원소를 추가(heappush)하거나,
기존의 리스트를 힙 구조로 만들어 주고(heapify) 시작한다.1) 빈 리스트 생성 + 원소 추가
# 빈 리스트 생성 heap_list = [] # 원소 추가 : heapq.heappush(리스트명, 원소) heapq.heappush(heap_list, 3) heapq.heappush(heap_list, 7) heapq.heappush(heap_list, 1) heapq.heappush(heap_list, 5) heapq.heappush(heap_list, 9) # 확인 print(heap_list) > [1, 5, 3, 7, 9]2) 기존 리스트 힙 구조로 변경
# 기존 리스트 heap_list = [3,7,1,5,9] # 힙 구조화 heapq.heapify(heap_list) # 확인 print(heap_list) > [1, 5, 3, 7, 9]
-
원소 삭제
1) root 노드 위치의 원소 리턴 후 삭제.# 최소힙 리스트 heap_list = [3,7,1,5,9] heapq.heapify(heap_list) # 원소 삭제 후 다시 힙 구조화 heapq.heappop(heap_list) # 리턴 후 삭제, list의 pop처럼. # 확인 print(heap_list) > [3, 5, 9, 7]
heapq에서 만드는 힙 구조는 '최소힙'이다. '최대힙'을 만들고 싶을 경우, 사람들은 수를 index를 음수로 만들어 tuple로 정렬하는 꼼수(?)를 사용한다. 그냥 모듈없이 구현할 수 있지만, 굉장히 긴 코드와.. 원리를 이해할 때 보는 것 외에는 굳이...? 싶은 마음인데, 또 내가 모르는 쓰는 이유가 있겠지..?
번외 - 힙(Heap)과 이진탐색트리(BST)의 공통점과 차이점
✅ 공통점
- 둘 다 이진트리
✅ 차이점
- 힙 : 최대값/최소값 검색을 위한 구조
- 각 부모 노드가 자식 노드보다 크거나 같음(최대 힙)/ 작거나 같음(최소 힙)
- 형제끼리는 조건이 없음 (왼쪽 자식 노드가 클 수도, 오른쪽 자식 노드가 클 수도 있음)
- 이진 탐색 트리 : 탐색을 위한 구조
- 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 값 순으로 큼.
오삽 : 오늘도 삽질