Heap 자료구조

- 완전이진트리, Max-Heap, Min-Heap, O(logn), 최악 O(n log n), 추가 메모리 불필요

 

- 완전이진트리 : 잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 트리
  1.완전이진트리를 최대 힙으로 구성
  2.삭제연산 > > Root Pop > 배열 최우측[내림차순 정렬]
  3.나머지 원소들에 대해 Max-Heap구성
  4.2~3과정 반복 수행, 내림차순 정렬 완성

 

1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다.

- 우선순위 큐 구현에 적합

- 문제풀이
   50, 30, 20, 15, 18
   5, 10, 20, 30, 40