목록힙정렬 (1)

말감로그

[알고리즘] 힙 정렬(Heap Sort)

힙 정렬이란 ? 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 이러한 두 값의 대소 관계가 일정하면 된다. 완전 이진 트리란? 노드를 삽입할 때 왼쪽부터 추가하는 이진트리(모든 노드의 차수가 2이하로 구성된 트리) 모든 부모와 자식 관계는 항상 부모의 값 >= 자식의 값 성립 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다. 따라서 힙은 형제의 대소관계가 정해져 있지 않으므로 부분 순서 트리(partical ordered tree)라고도 한다. 시간복잡도 - O(n log n) 단순 선택 정렬의 시간 복잡도 O(n^2) 이러..
이론/자료구조 2024. 2. 19. 23:35
이전 Prev 1 Next 다음