- 힙이란 우선순위 큐를 표현 한 완전이진트리
- 기본적으로 i 번째 자식의 요소는 2*i번(왼쪽) 2*i+1이다.
- 최대 힙 트리(MaxHeapify)나 최소힙 트리를 구성해 정렬
- 삽입
- Insert 트리의 끝부분에 값을 삽입하는 함수
- upHeap 삽입된 값의 위치를 찾아주는 함수
- 삭제
- DeleteMax 트리의 뿌리 부분에 존재하는 최대값을 제거
- downHeap대소 관계에 의해 트리를 재구성
- 최대힙 정렬 예
- N개의 노드에대한 완전 이진트리 구성 ->배열로
- 최대 힙 구성 부모노드가 자식노드보다 큰 트리 MaxHeapify
- 배열 마지막 값과 배열 첫번째 값을 교환
- 배열의 길이를 1줄인후 2,3반복()
- -> 2번을 수행하게 되면 배열의 첫번째 값에 가장큰 값 3번을 통해 큰값을 맨뒤로 보낸 후 맨 뒷값을 제외하고 2,3번을 다시 반복
- 복잡도는 O(nlgn)
Public void 힙 구조 만들기(Building a heap)
Public void 최대값 추출 (Extract-Max)
Public void 힙 소트(Heap Sort)
왜 A.lenth/2 부터 down to 하는 가 ?
package heapsort;
import java.sql.Array;
import java.util.Arrays;
import java.util.Iterator;
public class Heap {
// Building a heap 메소드는 부모노드가 자식보다 큰 값을 갔는 형태로 만들어줌
public static void Buildingheap(int[] arr) {
int len = arr.length;
int parent;// 자식을 갖는 부모노드
if(0<len){
for ( parent = len/2; parent > 0; parent--) {
Extract_max(arr,len,parent);
}
HeapSort(arr);
System.out.print (" " +arr[arr.length-1]);// stack이 쌓이기때문에 전에 실행하지 못했던 배열의 값들이 쌓인데
}
}
// 최대값 추출은 최상위 제일 큰 값을 뺐을때의 트리구조를 다시 완전이진트리인 힙구조로 바꿔줌
public static void Extract_max(int [] arr,int len,int parent) {//원래 배열,배열길이, 자식을 가지는 부모노드 인덱스
//TODO 최대 힙트리를 구성한다.
int temp;
parent = parent-1;
int left = parent*2+1;
int right = parent*2+2;
if(left==len-1){//왼쪽 자식 인덱스와 배열길이 값이 일치하면 마지막 부모노드는 왼쪽 자식만 갖는 부모그러므로 왼쪽자식과 부모만 비교한다.
if(arr[parent]<arr[left]){
temp=arr[parent];
arr[parent]=arr[left];
arr[left]=temp;
}
}
// 아니라면 둘다 자식을 갖는다 .
else{
if(arr[right]<arr[left]&& arr[parent]<arr[left]){
temp=arr[parent];
arr[parent]=arr[left];
arr[left]=temp;
}
else if(arr[left]<arr[right]&&arr[parent]<arr[right]){
temp=arr[parent];
arr[parent]=arr[right];
arr[right]=temp;
}
}
System.out.println("최대힙 구성 과정 : "+Arrays.toString(arr));
}
// 최대값들을 하나씩 빼어 정렬
public static void HeapSort(int [] arr) {
int last = arr.length-1;
int [] temparr = new int[last];
int temp;
temp=arr[0];
arr[0]=arr[last];
arr[last] = temp;
for (int i = 0; i < temparr.length; i++) {
temparr[i]=arr[i];
}
System.out.println("|최대값 교환 과정 후 마지막 노드 삭제| : "+Arrays.toString(temparr));
Buildingheap(temparr);
}
public static void main(String args[]){
int arr[]={ 3,9,1,2, 22,21,69,72 };
Buildingheap(arr);
}
}
