[알고리즘] 힙 정렬

[알고리즘] 힙 정렬

힙의 형태

완전 이진 트리 : 각 노드의 자식 수가 2 이하이며, Root 노드부터 Leaf 노드까지 빠짐없이 채워져있는 트리

최대힙 Max-Heap

부모 노드 > 자식 노드

Root 노트의 값이 가장 크다.

최소힙 Min-Heap

부모 노드 < 자식 노드

Root 노드의 값이 가장 작다.

힙 배열 저장 방식

Root 노드는 배열의 첫 번째에 저장

각 노드들은 레벨 별로 저장

▶ 부모 : 현재위치 / 2

▶ 왼쪽 자식 : 현재위치*2

▶ 오른쪽 자식 : 현재위치 *2+1

힙 배열 저장 방식

힙의 높이

O(logN)

힙 특성관리 Max-Heapify

노드가 입력으로 주어졌을 때 max-heap 특성이 유지되도록 바꾸는 연산

입력값이 흘러내리게 함.

수행시간 : O(logN)

Max-Heapify

힙 구조 만들기

입력받은 트리에 Max-Heapify를 반복 적용

Max-Heapify를 최대 O(n)번 호출

전체 수행시간은 O(NlogN)

최대값 추출

Heap에서 가장 큰 값을 제거하고 Max-Heap 구조를 복원하는 연산

① 루트노드 제거

② 리프노드를 루트 노드 위치로 이동

③ Max-Heapify 실행

힙 소트

① Max-Heap 구조 생성 : O(NlogN)

② 최대값 추출을 n번 반복 : O(NlogN)

③ 전체 수행시간 O(NlogN)

반응형

from http://hodubab.tistory.com/353 by ccl(S) rewrite - 2021-09-07 02:00:20