힙1 힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다. H[k] - 왼쪽 자식 노드 : H[2*k+1] - 오른쪽 자식 노드 : H[2*k+2] - 부모 노드 : H[(k-1) //2] 힙 (heap) : 힙 성질(heap property)를 만족하는 이진트리 힙 성질 1. 모양이 힙의 형태 (왼쪽부터 채운 형태) 2. 모든 부모 노드 키값은 자식 노드 키값보다 커야 함 힙의 루트노드에서는 가장 큰 값이다. A[0] 제공연산: 1. insert : O(logn) 2. find-max : return A[0] - O(1) 3. delete-max : O(logn) 참조 - .. 2021. 12. 31. 이전 1 다음
