힙 삽입
-
[알고리즘 개념] 힙 (heap)알고리즘 공부/알고리즘 개념 2020. 8. 11. 15:55
이진트리 : 모든 노드의 자식 노드가 2개 이하인 트리 구조 완전 이진트리 이진트리와 다르게 데이터가 루트 노드부터 시작하여 자식 노드가 왼쪽, 오른쪽 자식 노드 순서로 쌓이게 되는 트리를 말한다. 이진트리는 중간에 노드가 비어있을 수 있지만, 완전 이진 트리는 중간 노드가 비어있을 수 없는 형태이다. 힙 힙은 최대 힙과 최소 힙이 있다. 최대 힙은 구성하는 모든 노드가 '부모 노드가 자식 노드보다 크다'라는 규칙을 가진 것이다. 최소 힙은 반대로 구성하는 모든 노드에 대해 부모 노드가 자식 노드보다 작다는 규칙을 가진 것이다. 따라서 힙의 루트는 최댓값이나 최솟값이다. 따라서 힙은 최댓값과 최솟값을 쉽게 찾을 수 있는 자료 구조이다. 배열의 인덱스를 활용하여 자식 노드와 부모 노드를 찾기 쉽기 때문에 ..