자료구조_비선형구조 ① 트리 - 힙트리 HeapTree

 

(1)힙트리 Heap tree 

정렬에 사용되느 이진트리

항상 전이진 트리를 구성 

중복된 값을 허용 

힙은 최대값,최소값 검색을 위한 구조 

Max heap 최대 힙  : 부모 노드 키 > 자식 노드 키 

Min heap 최소 힙 : 부모 노드 키 < 자식 노드 키 

우선순위 큐를 위하여 만들어진 자료구조

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 

※ 완전이진트리 : 노드 삽입 할 때부터 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 

부모 노드의 값은 자식 노드의 값보다 큰 상태를 유지한다 

 

추가하기

---

왼쪽 하단부부터 노드가 채워지는 형태 

노드가 채워진다면 숫자 순서대로 채워진다

추가한다면 마지막 노드를 생성하고 부모 노드가 자신보다 클때까지 부모로 올라간다. 

 

 

삭제하기

---

 

상단 데이터 삭제시 

 

하단부 왼쪽에 위치한 노드를 뿌리 노드로 이동 

뿌리 노드 값이 자식 노드보다 작을경우

뿌리 노드의 자식노드 중 가장 큰 값을 가진 노드와 뿌리 노드 위치 바꿔주는 작업 반복

시간복잡도

---

 

시간 복잡도 Big O 표기법 이란 

불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다 

 

Bio O 표기법	내용	시간복잡도 빠른순
O(1)	입력자료의 수에 관계없이 일정한 실행시간을 갖음	1
O(logn)	입력자료의 수에 따라 시간이 흐를수록 시간이 조금씩 증가	2
O(n)	입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우 - 입력자료마다 일정 시간 할당	3
O(nlogn)	큰 문제를 일정 크기 갖는 문제로 쪼개고(logn+logn+ .. + logn) 다시 그것을 모으는 경우	4
O(n^2)	이중 루프내에서 입력 자료를 처리할 때	5
O(n^3)	삼중 루프 내에서 입력자료 처리할 때	6
O(2^n)		7
O(n!)		8

 

이진 트리로 구성되어 있기 떄문에 노드의 갯수가 

값을 제거하거나 추가하면 힙을 갱신하는 동안 O(logN) 소요

 

 

힙 의 시간복잡도	삽입 add	O(logn)
	삭제	O(logn)
	최소값 접근	O(1)