MIT - Introduction to Algorithms - Lecture 4 Heaps and Heap Sort 힙과 힙 정렬 Review

MIT - Introduction to Algorithms

- Lecture 4 Heaps and Heap Sort

힙과 힙 정렬 Review

Copyright to MIT & Srini Devadas & Erik Demaine
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/

code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml

한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/

Priority Queues 우선순위 큐
Heaps 힙
Heapsort 힙 정렬

2011년까지 개발된 가장 작은 자료구조들 중의 하나는 힙

삽입 정렬이나 합병 정렬과는 다르고 좋은 성질들을 가지고 있음

왜 힙을 배워야하는지?

ADT(Abstracted Data Type) 추상적인 자료형
우선순위 큐는 운영체제의 우선 순위에 따른 실행을 위해 사용이 가능하다
에이징 기법으로 후순위의 작업 우선순위를 조정시켜줄 수도 있음

Heap : 배열 구조, 우선 순위 큐를 구현 but nearly 완전 이진트리
nearly가 붙은 이유 : 예시에서처럼 완전 이진트리의 경우 15개가 있어야하지만 10개만 표현할 때 부족한 가지들이 있기 때문
위 그림은 이 강좌에서 계속 생각해야하는 그림
힙 구조가 좋은 것은 트리 형태의 배열로 많은 일을 할 수 있기 때문

Heap을 보통 max Heap으로 이해해도 무방
다만 Binary Tree와 Heap은 같지 않은 것 같다.
Heap은 Min, Max기준으로 정렬이 가능하기 때문

Max-Heap : property : The key of a node is >= the keys of its children
recursive

어떤 작업이 최대 힙에서 수행? 가장 큰 요소를 찾는 max()
=> 간단히 실행이 가능 : 단순히 최대값을 반환할 뿐 힙의 수정이 없음
extract_max()의 경우 최대힙에서 간단하게 수행할 수 없음

불변성은 최대 힙 특성
힙을 수정하면서 최대 힙 특성을 유지하고자 함
어떻게?

Heap Operations

build_max_heap : produce a max-heap from an unordered array
max_heapify : correct a single violation of the heap property in a subtree at its root
insert, extract_max, heapsort

build_max_heap를 위해서는 먼저 max_heapify가 선행
Max_heapify

Assume that the trees rooted at left(i) and right(i) are max-heaps
If element A[i] violates the max-heap property, correct violation by “trickling” element A[i] down the tree, making the subtree rooted at index i a max-heap

Max_Heapify Complexity복잡도 : O(log(n))
2가지 중요한 점 :
1. 첫 번째 시각화한 것이 완전 이진 트리라는 점 (not unbalnaced tree)
높이가 log n
2. build_max_heap 가정
힙에는 규칙을 위반한 요소가 하나 있다는 것
만약 이 가정이 없다면 O(n)
알고리즘을 더 효율적으로 만드는 조건, 구현을 더 쉽게 함

후에 배열을 정리하기 위해 extract_max()를 사용