Heap
2019. 03 .10 (Mon)
완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조
이진 탐색 트리처럼 탐색을 위한 순서가 불필요
완전 탐색 트리이어야 함
배열로 구현시 0인덱스는 비우고 구현
Priority Queue에 적용
PQ를 Queue로 구현하면 Selection Sort를 사용하기 때문에 속도가 많이 저하됨(O(n^2))
PQ를 힙으로 구현하면 탐색, 삽입에 대해 이진 연산을 하기 때문에 성능이 더욱 상승(O(log(n)))
1. Max Heap
모든 자식노드 key는 부모노드의 key의 값보다 작다
최대값을 빠르게 구하는데 사용
2. Min Heap
모든 자식노드 key는 부모노드의 key의 값보다 크다
최소값을 빠르게 구하는데 사용
3. 연산
삽입
- 트리의 마지막 위치에 노드 삽입
- 부모 노드의 값과 비교하여 규칙과 맞는지 확인
- 규칙에 어긋날 경우 부모노드와 위치 변환
삭제
루트 노드의 원소만을 삭제할 수 있다
삭제 후 마지막 노드가 루트 노드를 대신함
이후 규칙에 맞게 자리바꾸기 실행
- 최대 힙일경우 자식 노드중 큰 값과 교환