import java.util.ArrayList;
import java.util.Collections;
public class Heap {
// 힙(Heap) 이란?
// 힙 : 데이터에서 최대값과 최소값을 빠르게 찾아내기 위해 고안된 완전 이진 트리(Complete Binary Tree)
// 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
//
// 힙을 사용하는 이유 :
// 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
// 이에 반해 , 힙에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(logn)이 걸림
// 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨
// 힙(Heap) 구조
// 힙은 최대값을 구하기 위한 구조(최대 힙, Max Heap)와, 최소값을 구하기 위한 구조(최소힙, MinHeap)로 분류할 수 있음
// 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조 임
// 1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다.(최대 힙의 경우)
// 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같음
// 2. 완전 이진트리 형태를 가짐
//
// 힙과 이진 탐색 트리의 공통점과 차이점
// 공통점 : 힙과 이진 탐색 트리는 모두 이진트리이다.
// 차이점 :
// 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
// 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
// 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
// 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음
// 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값을 검색을 위한 구조 중 하나로 이해하면 된다.
// 힙(Heap) 동작
// 데이터를 힙 구조에 삽입, 삭제하는 과정
//
// 힙에 데이터 삽입하기 - 기본 동작
// 힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입
//
// 힙에 데이터 삽입하기 - 삽입할 데이터가 힙의 데이터보다 클 경우(Max Heap의 예)
// 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐
// 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복합(swap)
// 힙의 데이터 삭제하기(Max Heap의 예)
// 보통 삭제는 최상단 노드(root 노드)를 삭제하는 것이 일반적이다
// 힙의 용도는 최대값 또는 최소값을 root노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸수 있도록 하는 것임
// 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드(일반적으로 가장 마지막에 추가한 노드)를 root노드로 이동
// root 노드의 값이 child node보다 작을 경우, root 노드의 child node중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을
// 반복한다(swap)
// 힙구현
// 힙과 배열
// 일반적으로 힙 구현시 배열 자료구조를 활용한다
// 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해 root노드 인덱스 번호를 1로 지정하면 구현이 좀더 수월하다.
// 부모 노드 인덱스 번호(parent node's index) = 자식 노드 인덱스 번호(child node's index)/2
// Java에서는 / 연산자로 몫을 구할 수 있음
// 왼쪽 자식 노드 인덱스 번호(left child node's index) = 부모 노드 인덱스 번호(parent node's index)*2
// 오른쪽 자식 노드 인덱스 번호(right child node's index) = 부모 노드 인덱스 번호(parent node's index)*2+1
// 힙에 데이터 삽입 구현(Max Heap 예)
//
// 힙 클래스 구현1
// import java.util.ArrayList를 활용해서 구현
public ArrayList<Integer> heapArray = null;
public Heap(Integer data){
heapArray = new ArrayList<Integer>();
heapArray.add(null); //루트 노드
heapArray.add(data);
}
// 힙 클래스 구현2 -insert1
// 인덱스 번호는 1번부터 시작하도록 변경
public boolean insert(Integer data){
/*if(heapArray == null){ //힙이 존재하지 않다면
heapArray = new ArrayList<Integer>();
heapArray.add(null); //루트노드
heapArray.add(data);
}else{
heapArray.add(data);
}
return true;*/
Integer inserted_idx, parent_idx;
if(heapArray == null){
heapArray = new ArrayList<Integer>();
heapArray.add(null);
heapArray.add(data);
return true;
}
this.heapArray.add(data);
inserted_idx = this.heapArray.size() -1; //인덱스의 길이 -1 = 마지막 삽입한 데이터의 인덱스번호
while(this.move_up(inserted_idx)){
parent_idx = inserted_idx/2;
Collections.swap(this.heapArray, inserted_idx, parent_idx);
inserted_idx = parent_idx;
}
return true;
}
public boolean move_up(Integer inserted_idx){
if(inserted_idx <= 1){
return false; //루트노드보다 작기 때문에 종료
}
Integer parent_idx = inserted_idx/2; //부모 노드의 인덱스 번호 얻어오기
if(this.heapArray.get(inserted_idx) > this.heapArray.get(parent_idx)){ //inserted_idx가 부모보다 크다면
return true; //스왑을 해줘야 한다
}else{
return false; //스왑을 안해도 된다
}
}
// 힙클래스 구현3 -insert2
// 삽입한 노드가 부모 노드의 값보다 클 경우, 보모 노드와 삽입한 노드 위치를 바꿈
// 삽입한 노드가 루트 노드가 되거나, 부모 노드보다 값이 작저나 같을 경우까지 반복
//
// 특정 노드의 관련 노드 위치 알아내기
// 부모 노드 인덱스 번호 : 자식 노드 인덱스 번호 /2
// 왼쪽 자식 노드 인덱스 번호 : 부모 노드 인덱스 번호 *2
// 오른쪽 자식 노드 인덱스 번호 : 부모 노드 인덱스 번호 *2 +1
// 힙 구현에 사용된 Collections.swap()메서드 사용법 이해하기
// swap(스왑) 이란 , 두 데이터의 위치를 맞바꾸는 것을 의미한다.
// swap함수를 별도로 구현할 수도 있지만, JAVA에서는 Collection 패키지에서 swap()메서드를 제공해주고 있다
// 하나의 배열 안에 있는 두 데이터의 위치를 서로 맞바꾸고 싶을 때 사용 가능
//
// import java.util.Collections;
//
// Collections.swqp(List list, int a, int b)
// list : 스왑할 데이터들이 들어 있는 배열 변수
// a : 스왑할 데이터 인덱스 번호
// b : 스왑할 데이터 인덱스 번호
// 힙 데이터 삭제 구현(Max Heap 예)
//
// 힙 클래스 구현 4 - delete1
// 보통 삭제는 최상단 노드(root 노드)를 삭제하는 것이 일반적임
// 힙의 용도는 최대값 또는 최소값을 root노드에 놓아서 , 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임
public Integer pop(){
Integer returned_data, popped_idx, left_child_popped_idx, right_child_popped_idx;
if(this.heapArray == null){
return null;
}else{
//return this.heapArray.get(1); //값을 가져오기만 하지 삭제하지는 않음
returned_data = this.heapArray.get(1); //삭제할 노드 값을 저장
this.heapArray.set(1, this.heapArray.get(this.heapArray.size()-1)); //마지막에 삽입한 노드 값을 루트노드로 설정
this.heapArray.remove(this.heapArray.size()-1); //마지막 노드를 루트로 옮겼으니 원래있던 마지막 노드는 삭제
popped_idx = 1; //삭제된 노드의 인덱스 번호 (루트 노드이므로 1)
while(this.move_down(popped_idx)){ //swap
left_child_popped_idx = popped_idx * 2; //왼쪽 노드
right_child_popped_idx = popped_idx * 2+1; //오른쪽 노드
//Case 2 : 오른쪽 자식 노드만 없을 때
if(right_child_popped_idx >= this.heapArray.size()){ //size보다 크거나 같으면 값이 존재하지않는다
if(this.heapArray.get(popped_idx) < this.heapArray.get(left_child_popped_idx)){
//왼쪽 노드가 더 크다면 swap 진행
Collections.swap(this.heapArray, popped_idx, left_child_popped_idx);
popped_idx = left_child_popped_idx;
}
}else{ //Case 3 : 왼쪽/오른쪽 자식 노드가 모두 있을 때
if(this.heapArray.get(left_child_popped_idx) > this.heapArray.get(right_child_popped_idx)){
if(this.heapArray.get(popped_idx)< this.heapArray.get(left_child_popped_idx)){
//왼쪽 자식 노드가 오른쪽 자식 노드보다 더 크면
Collections.swap(this.heapArray, popped_idx, left_child_popped_idx);
popped_idx = left_child_popped_idx;
}
}else{ //오른쪽 자식 노드가 왼쪽 노드보다 더 크면
if(this.heapArray.get(popped_idx)< this.heapArray.get(right_child_popped_idx)){
Collections.swap(this.heapArray, popped_idx, right_child_popped_idx);
popped_idx = right_child_popped_idx;
}
}
}
}
return returned_data;
}
}
// 힙 클래스 구현 4 - delete2
// 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드(일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동
// root 노드의 값이 child node보다 작을 경우, root 노드의 child node중 가장 큰 값을 가진 노드와 root 노드의
// 위치를 바꿔주는 작업을 반복함(swap)
// 구현을 위한 move_down 메서드 작성하기
public boolean move_down(Integer poped_idx){
Integer left_child_poped_idx, right_child_poped_idx;
left_child_poped_idx = poped_idx * 2; //
right_child_poped_idx = poped_idx *2 +1;
//Case 1 : 왼쪽 자식 노드도 없을 때(자식 노드가 하나도 없을 때)
if(left_child_poped_idx >= this.heapArray.size()){
return false;
}//Case2 : 오른쪽 자식 노드만 없을 때
else if(right_child_poped_idx >=this.heapArray.size()){
if(this.heapArray.get(poped_idx) < this.heapArray.get(left_child_poped_idx)){
return true; //왼쪽 노드가 pop의 값보다 크면 swap을 진행
}else{
return false; //pop값이 더 크면 swap을 하지 않음
}
//Case3 : 왼쪽 / 오른쪽 자식 노드가 모두 있을 때
}else{ //왼쪽과 오른쪽노드의 대소 비교
if(this.heapArray.get(left_child_poped_idx) > this.heapArray.get(right_child_poped_idx)){
//왼쪽이 더 크면
if(this.heapArray.get(poped_idx) < this.heapArray.get(left_child_poped_idx)){
return true; //왼쪽 노드와 비교해 왼쪽 노드가 크면 swap진행
}else{
return false; //왼쪽 노드가 작으면 swap진행하지 않음
}
}else{ //오른쪽이 왼쪽 노드보다 더 크면
if(this.heapArray.get(poped_idx) < this.heapArray.get(right_child_poped_idx)){
return true; //오른쪽 노드와 비교해 오른쪽 노드가 더 크면 swap진행
}else{
return false; //오른쪽 노드가 더 작으면 swap 진행하지 않음
}
}
}
}
public static void main(String[] args) {
/*Heap heapTest = new Heap(1);
System.out.println(heapTest.heapArray); //[null, 1]
System.out.println("###################################");
heapTest.insert(2);
heapTest.insert(3);
heapTest.insert(4);
heapTest.insert(5);
System.out.println(heapTest.heapArray); //[null, 1, 2, 3, 4, 5]
System.out.println("###################################");
ArrayList<Integer> heapArray = new ArrayList<Integer>(); //swap 테스트
heapArray.add(1);
heapArray.add(2);
System.out.println("변경전 : "+heapArray);
Collections.swap(heapArray,0,1);
System.out.println("변경후 : "+heapArray);
System.out.println("###################################");*/
Heap heapTest = new Heap(15);
heapTest.insert(10);
heapTest.insert(8);
heapTest.insert(5);
heapTest.insert(4);
heapTest.insert(20);
System.out.println(heapTest.heapArray); //[null, 20, 10, 15, 5, 4, 8] heapArray=public
heapTest.pop();
System.out.println(heapTest.heapArray); //[null, 15, 10, 8, 5, 4]
// 힙(Heap)의 시간 복잡도
// depth(트리의 높이)를 h라고 표기한다면
// n개의 노드를 가지는 heap에 데이터 삽입 또는 삭제시, 최악의 경우 root노드에서 leaf노드까지 비교해야 하므로
// h= logn에 가까우므로 , 시간 복잡도는 O(logn)
// 한번 실행시마다 ,50%의 실행할 수도 있는 명령을 제거한다는 의미, 즉 50%의 실행시간을 단축
// 시킬수 있다는 것을 의미함
}
}