[컴퓨터알고리즘] 5장 - 힙 정렬

힙 정렬

- 최악: O(nlgn)

- 제자리 정렬.

- Heap 자료구조 특징

- Heapify(), BuildingHeap(), HeapSort()

- 우선순위 큐

 

Heap 자료구조

- 힙은 완전이진트리 (맨 마지막 level 제외 꽉 차있는 이진 트리)

  - 트리는 무조건 부모/자식 단일 연결. 상향: 부모, 하향: 자식.

- 배열로 구현된다. (노드에 1번부터 번호 붙어있. 삽입 순서=배열 인덱스. A[0] 안쓰는 경우로 설명함.)

- root 노드 A[1]

- i번째 노드 A[i]: 부모 노드 A[i/2], 왼쪽 자식 노드 A[2i], 오른쪽 자식 노드 A[2i+1]

 

Heap 용어

- 노드의 height: 리프부터 노드까지의 간선 개수

- 트리의 height: 루트노드의 높이

- 노드의 depth: 루트부터 노드까지의 간선개수 (루트노드의 깊이=0)

 

n개 요소가 있는 힙의 높이는 ⌊lg(n) ⌋

- 모든 힙 연산은 힙의 높이에 비례한다.

 

Heap의 특성

* Max-Heap: 항상 부모가 큼

* Min-Heap: 항상 부모자 작음

- 이진트리의 subtree도 이진트리이다.

 

Heap 연산

- MAX 추출 알고리즘