힙 구조
- 맥스 힙 특성 ( A[PARENT(i)]>=A[i] )
- 부모 노드의 값은 항상 자식의 노드의 값보다 크다.
- 따라서 전체 트리의 Root 노드 값이 가장 크다.
- 또한 각 하위 트리 구조의 Root 노드가 가장 큰 값을 가진다.
- 최소 힙 특성
- 부모노드의 값보다 크다.
- 힙구조
PARENT(i)
Return[i/2]
LEFT(i)
Return[2i]
RIGHT(i)
Return2i+1
- 노드의 높이
Simple path vertax가 곂치지 않고 제일 쉽게 내려가는 경우
- 힙의 높이
O(logN)
2. 힙특성 관리
- Max-Heapify 의 수행시간.,T(n)
- N을 하위 트리의 노드의 개수라고 할 때,
- '노드의 값을 바꿀때 수행시간: O(1)
- 힙의 높이 O(h)=O(lgn)
- 따라서 전체 수행시간은 : O(lgn)
3.학습정리
- 힙정렬 알고리즘 시간 복잡도는 nlogn
- Max 힙은
- 부모노드가 자식노드보다 커야한다.
- 완전 이진트리여야 한다.
- 그 조건을 만족하게 만들어 주는 것을 Max-Heapify
- 힙 구조 만들고 최대값추출 함수를 이해하고 힙정렬 이해하기
Soudo code
BUILD-MAX-HEAP
A.heap-size =A.length
For i=|a.length/2| downto 1
MAX-HEAPIFY(A,i)
왜 다운을 하지 ? --1로
만약 root 노드부터 간다고 생각하면
그때마다 다시 해줘야 하기 때문에
그래서 맨 아래서 부터 하면 여러 번 수행할 필요없이 해당되는 서브트리만 하면 되기때문에.
왜 배열길의에 절반이지 ?
i 노드를 기준으로 부모는 i/2 이고 왼쪽 자식노드는 2i번 노드에 있고 오른쪽은 2i+1노드위치에 있다.
자식을 가지는 첫번째 노드가 n/2위치에 있기 때문에 그거부터 시작해서 --1씩 감소한다.
최대값 추출
Heap에서 가장큰 값을 차례대로 뽑아 내기만 하면 정렬이 완성된다 .
Root 노드를 빼면 트리구조가 망가지기 때문에
가장 마지막에 있는 값을 root 값과 교체를 한다.
교체한 최대값은 트리관계를 끊어 버린다.
- 힙정렬
힙소트
HeapSort(A)
Build-max-heap(A)
For i = [_A.length/2] down to 2
Exchang A[1] with A[i]
A.heap-size = A.heap-size-1 // 힙사이즈가 하나씩 줄기 때문에 전체 배열 길이를 하나씩 줄여야 한다.
Max-Heapify(A,1)
왜 2까지 가지 ?
전체트리에서 키값이 하나만 남아있으면 할 필요가 없으므로 2까지 간다.
수행시간
매번 build-max-heap을 수행하는 시간 nlogn
Extract-max 를 n번 반복
수행시간을 nlogn
학습정리
입력받은것을 max heap을 만들고 heapify를 통해 최대값을 순서대로 뽑아내어 정렬을 완성한다.
수행시간은 nlogn
