이진 힙(Binary Heap)
= heap
- 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조
- 시간 복잡도는 O(log n) 이다.
이진 힙 특징
- 완전하다 : 트리가 왼쪽에서 오른쪽으로 다 채워짐 = 완전 이진 트리(Complete Binary Tree)
https://garysummers.tistory.com/124
Tree
- 비선형 자료구조 - 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조 - 가지를 늘려가며 표현하게 된다. Tree의 구조 - 노드(node) : 2, 7, 5, 2, 6, 5, 11, 4, 9와 같은 요소들 - 간선(edge) : 노..
garysummers.tistory.com
- *힙 순서 속성을 만족한다
최대 힙(Max Heap)일 때
- 모든 노드는 그 자식노드보다 크거나 같다
- 루트 노드는 항상 가장 큰 노드이다 => 최대 힙
최소 힙(Min Heap)일 때
- 모든 노드는 그 자식노드보다 작거나 같다
- 루트 노드는 항상 가장 작은 노드이다.
힙 순서 속성
- 힙은 제한된 순서 정보를 제공한다.
- 각각의 경로는 정렬되어 있고, 서브트리는 정렬되어 있지 않다. => binary heap != binary search tree
Binary Heap과 BST의 차이
Binary Heap은 좌, 우 자식노드 보다 값이 작다
BST는 좌 자식노드보다 크고, 우 자식노드보다 작다
- binary heap은 완전한 트리이다. -> 우측 가장 아래를 제외하곤 다 사용된다.
--참조
https://courses.cs.washington.edu/courses/cse373/06sp/handouts/lecture10.pdf
https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)
힙 (자료 구조) - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다. 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게
ko.wikipedia.org
https://yoongrammer.tistory.com/80
[자료구조] 힙 (Heap) or 이진 힙(binary heap)
목차 힙 (Heap) or 이진 힙(binary heap) 알아보기 힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으..
yoongrammer.tistory.com
'CS' 카테고리의 다른 글
| Hash Table (0) | 2022.10.01 |
|---|---|
| Red-Black Tree (0) | 2022.10.01 |
| Tree (0) | 2022.09.24 |
| Array vs Linked List (0) | 2022.09.23 |
| Stack vs Queue (0) | 2022.09.23 |