728x90 시간 복잡도1 힙 정렬(Heap Sort) 힙 정렬(Heap Sort)은 큌 정렬(Quick sort)과 병합 정렬(Merge Sort)과 같은 시간 복잡도 O(N*logN)를 가지고 있다. 힙 트리를 이용하는 정렬 방법이다. 힙 트리란 힙 트리의 조건 중 부모 노드의 값은 항상 자식 노드(하위 노드)의 값보다 크거나 작아야 한다. 힙 트리는 위의 조건은 만족하는 정렬은 두가지 뿐이다. 최대 힙(Max Heap), 최소 힙(Min Heap) 힙 트리 구조의 자녀 트리 사이에는 대소관계는 정해지지 않는다. 또한 힙 트리는 완전 이진 트리를 조건으로 가지고 있어야 한다. 왼쪽부터 차근차근 채워나가며 1~n까지 만들어지는 트리구조이다. 완전 이진 트리의 장점은 트리를 배열로 쉽게 구현이 가능하며, 부모 노드와 자식 노드 간에 관계를 수식화 할 수 있다.. 2021. 5. 14. 이전 1 다음 728x90
