코린이의 개발 일지

힙이란? → 이진트리의 한 종류 (이진 힙 - binary heap 이라고도 부른다.) 루트 (root) 노드가 언제나 최댓값 또는 최솟값을 가진다. 최대 힙 (max heap) 최소 힙 (min heap) 완전 이진트리여야 함 → 재귀적으로도 정의 된다. (어느 노드를 루트로 하는 서브트리도 모두 최대 힙) → 왼쪽과 오른쪽 자식을 비교하는 기준은 없다. 이러한 개념을 바탕으로 힙 연산을 코드 구현 해보자. 먼저 연산을 정의하자면 init() - 빈 최대 힙을 생성 insert(item) - 새로운 원소를 삽입 remove() - 최대 원소 (root node) 를 반환 (그리고 동시에 이 노드를 삭제) 배열을 이용한 이진 트리의 표현 노드 번호 m을 기준으로 왼쪽 자식의 번호 : 2*m 오른쪽 자식의..