이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.
- 힙의 특성을 만족하는 거의 완전한 트리(Almost Complete Tree)인 트리 기반 자료구조
- 힙의 특성
- 부모가 항상 자식보다 작거나 같다 - 거의 완전한 트리
- 완전 트리(Complete Tree)와 같은 의미
- 포화 트리(Perfect Tree)에서 pefect와 complete의 단어적 의미 충돌로 인해 생겨난 말인듯 하다
https://en.wikipedia.org/wiki/Binary_tree
- 힙의 특성
Binary tree - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search Limited form of tree data structure Not to be confused with B-tree. A labeled binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and no
en.wikipedia.org
Some authors use the term complete to refer instead to a perfect binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.
- 파이썬에서 heap
- 최소 힙만 구현되어 있음
- 최소 힙 : 루트에 최소값이 오는 힙 구조 - 우선순위 큐 ADT는 힙, 힙은 배열로 구현
- 배열 -> 힙 -> 우선순위 큐
- 최소 힙만 구현되어 있음
- 힙의 특징
- 이진 힙(Binary heap)
- 자식이 둘인 힙
- 대부분 이진 힙이 사용 - 힙이라는 자료구조는 힙 정렬의 부산물이라고 함
- 완전 이진 트리
- 레벨의 노드가 2배씩 증가
- 배열로 구현시 이를 이용하여 인덱스를 구함
- 이진 힙(Binary heap)
- 배열로 구현된 힙
- 인덱스를 1부터 시작
- 계산이 편함
- 왼쪽 노드 : i * 2 / 오른쪽 노드 : i * 2 + 1
- 인덱스를 1부터 시작
- 힙의 사용
- 우선순위 큐
- 다익스트라 알고리즘 - 최소 신장 트리
- 프림 알고리즘 - 적절한 중간 레벨 노드 추출
- 중앙값의 근사값
- 우선순위 큐
- 힙의 연산
- 삽입
- 가장 마지막 인덱스에 삽입 (완전 이진트리 특성 지키기)
- 업힙(up-heap) : 부모 노드보다 작을 경우 인덱스를 바꾸는 과정을 반복 (힙의 특성 지키기)
- log n - 추출
- 루트 노드 pop
- 가장 마지막 인덱스의 노드를 첫 인덱스(루트)에 위치시킴
- 다운힙(down-heap) : 옮긴 루트노드가 자식노드보다 크면 인덱스를 바꾸는 과정을 반복 (힙 특성 지키기)
- 다운힙은 왼쪽 자식부터 비교 (완전 이진트리 특성 지키기)
- log n
- 삽입
- BST와 비교
- BST는 좌/우 관계를 보장
- 힙은 상/하 관계를 보장
- BST는 삽입/탐색 모두 O(log n)
- 힙은 최소값 탐색시 O(1)
'책읽기' 카테고리의 다른 글
[파이썬 알고리즘 인터뷰] 16장 - 트라이 (0) | 2021.08.05 |
---|---|
[파이썬 알고리즘 인터뷰][HEAP] 배열의 K번째 큰 요소 (0) | 2021.08.05 |
[쉽게 배우는 데이터 통신과 컴퓨터 네트워크](요약)[Chapter-2] 네트워크 모델 (0) | 2021.08.04 |
[파이썬 알고리즘 인터뷰][트리] 전위,중위 순회 결과로 이진 트리 구축 (0) | 2021.08.04 |
[파이썬 알고리즘 인터뷰][BST] 이진 탐색 트리 노드 간 최소 거리 (0) | 2021.08.04 |