알고리즘/개념 정리
-
[JAVA] 자료구조 Heap & Heap sort (힙 & 힙 정렬) + 구현알고리즘/개념 정리 2024. 2. 23. 18:00
Heap 자료구조 란? - 데이터에서 최댓값 과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리 시간 복잡도 : O(logN) 이진 트리의 개념 - node : 각각의 값을 노드라고 부름 - root : 뿌리 노드, 레벨 0, 가장 최상단 노드로 부모 노드가 존재하지 않는 노드 - parent node : 부모 노드, 아래에 자식 노드를 가지고 있는 노드 - child node : 부모 노드로 뻗어나온 하위 노드 완전 이진 트리의 일종으로, 왼쪽으로부터 자료구조를 채워나가는 형태 오른쪽은 비어있는 경우가 있을 수 있음 1차원 배열로 나타낼 수 있음 -> 정렬이 가능한 이유 배열로 구현 시에, 인덱스 1로 시작하는 것으로 구현하면 편리함 (0으로 시작해도 무관) 중복 값 허용 (부모 노드의 인덱스) = ..