힙정렬1

• 

  210629 힙 정렬(heap sort) 우선 힙(heap) 이라는 구조에 대해서 먼저 이야기하면, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨 Complete(or left - complete) binary tree 로 표현 가능 * 가장 낮은 레벨 제외하고 full, 가장 낮은 레벨은 왼쪽부터 채워진 트리 * 우선 순위 큐(Priority Queue)를 구현할 수 있는 자료구조 A가 B의 부모 노드이면, A의 키(Key) 값과 B의 키(Key) 값 사이에는 대소 관계 성립 즉 루트에서 임의의 리프노드( 자식이 없는 노드) 까지 경로는 항상 정렬되어 있다 이진트리는 일반적으로 포인터 사용하여 저장 but left - complete라 배열 사용 가능 두가지 종류 부모 노드의 키 값이 자식 노드의 것 보다 항상 크면 = 최대 힙.. 미가공 필기(알고리즘) 2021. 6. 30.