힙2 배열을 이용한 힙(Heap) 구현 배열을 이용한 힙(Heap) 구현 배열을 이용했을때의 특징 힙의 삽입 과 삭제 연산이 더 빠르다. 노드의 주솟값을 계산할 수 있어 원하는 노드에 빨리 접근할 수 있다. 힙은 완전 이진 트리(Complete binary tree)이기 때문에 낭비되는 빈 노드가 적어 공간의 낭비가 적다. 배열의 위치 인덱스와 히프 루트 노드의 위치 인덱스의 값은 1 노드 i 의 부모 노드 인덱스 = [i / 2] , i>1 일때 ex) [5 / 2] = [2.5] = 2 노드 i 의 왼쪽 자식 노드 인덱스 = 2 * i 노드 i의 오른쪽 자식 노드 인덱스 = (2 * i) + 1 Max Heap 에 데이터 삽입하기 기본 원리 새로운 노드를 마지막 노드 옆에 삽입한다. 새로운 노드의 값을 부모 노드의 값과 비교하여 위치를 이.. 2020. 6. 15. 자료구조 힙(Heap) 알아보기 자료구조 힙(Heap) 알아보기 힙(Heap)은 무엇인가? 힙은 완전 이진 트리(Complete binary tree)의 한 종류이다. 완전 이진 트리에는 마지막 레벨을 제외하고는 빈 노드가 존재하지 않는다. 따라서 배열로 구현하기에 적합한 이진 트리이다. 루트 노드가 그 트리의 최댓값 혹은 최솟값을 가진다. 루트 노드가 트리의 최댓값을 가지면 최대 힙(Max heap) 루트 노드가 트리의 최솟값을 가지면 최소 힙(Min heap) 힙의 종류 최대 힙 (Max heap) 최대 힙은 각 노드의 값이 자식 노드의 값보다 크거나 같은 트리이다. 부모 노드의 Key 값 >= 자식 노드의 Key 값 루트 노드의 Key 값 = 트리의 최댓값 최소 힙 (Min heap) 최소 힙은 각 노드의 값이 자식 노드의 값보다.. 2020. 6. 14. 이전 1 다음
