1.
힙 이란?
•
힙 : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
•
완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
•
힙을 사용하는 이유
◦
배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
◦
이에 비해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸림
◦
우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨
2.
힙(Heap) 구조
•
힙은 최대값을 구하기 위한 구조(최대 힙,Max Heap)와, 최소값을 구하기 위한 구조(최소 힙,Min Heap)로 분류할 수 있음
•
힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임
1.
각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다.(최대 힙의 경우)
•
최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
2.
완전 이진 트리 형태를 가짐
•
힙과 이진 탐색 트리의 공통점과 차이점
◦
공통점 : 힙과 이진 탐색 트리는 모두 이진 트리임
◦
차이점 :
▪
힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
▪
이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
▪
힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
◦
이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨
3.
힙 동작
•
데이터를 힙 구조에 삽입, 삭제 하는 과정을 그림을 통해 선명하게 이해하기
•
힙에 데이터 삽입하기 - 기본 동작
◦
힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입
•
삽입 - 삽입할 데이터가 힙의 데이터보다 클 경우(Max Heap의 예)
◦
먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐
◦
채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함(Swap)
•
힙의 데이터 삭제하기(Max Heap의 예)
◦
보통 삭제는 최상단 노드(root)를 삭제하는 것이 일반적임
▪
힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임
◦
상단의 데이터 삭제 시, 가장 최하단부 왼쪽에 위치한 노드(일반적으로 가장 마지막에 추가한 노드)를 root로 이동
◦
root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함(Swap)
4.
힙 구현
•
힙과 배열
◦
일반적으로 힙 구현시 배열 자료구조를 활용함
◦
힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀 더 수월함
▪
부모 노드 인덱스 번호(parent node’s index) = 자식 노드 인덱스 번호(child node’s index)/2
▪
왼쪽 자식 노드 인덱스 번호(left child node’s index) = 부모 노드 인덱스 번호 *2
▪
오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1
•
힙에 데이터 삽입 구현
public class Heap{
public ArrayList<Integer> heapArray = null;
public Heap (Integer data) {
heapArray = new ArrayList<Integer>();
heapArray.add(null);
heapArray.add(data);
}
}
Java
복사
Heap heapTest = new Heap(1);
System.out.println(heapTest.heapArray);
Java
복사
•
힙 클래스 구현2 - insert 1
◦
인덱스 번호는 1번부터 시작하도록 변경
public class Heap{
public ArrayList<Integer> heapArray = null;
public Heap (Integer data) {
heapArray = new ArrayList<Integer>();
heapArray.add(null);
heapArray.add(data);
}
public boolean insert(Integer data){
if(heapArray == null){
heapArray = new ArrayList<Integer>();
heapArray.add(null);
heapArray.add(data);
}else{
heapArray.add(data);
}
return true;
}
}
Java
복사
•
힙 클래스 구현3 - insert2
◦
삽입한 노드가 부모 노드의 값보다 클 경우, 부모 노드와 삽입한 노드 위치를 바꿈
◦
삽입한 노드가 루트 노드가 되거나, 부모 노드보다 값이 작거나 같을 경우 까지 반복
public class Heap{
public ArrayList<Integer> heapArray = null;
public Heap (Integer data) {
heapArray = new ArrayList<Integer>();
heapArray.add(null);
heapArray.add(data);
}
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)){
return true;
} else {
return false;
}
}
public boolean insert(Integer data){
if(heapArray == null){
heapArray = new ArrayList<Integer>();
heapArray.add(null);
heapArray.add(data);
}else{
this.heapArray.add(data);
inserted_idx = this.heapArray.size()-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;
}
}
Java
복사
•
힙 클래스 구현 4 - delete1
◦
보통 최상단 노드를 삭제하는 것이 일반적임
▪
힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임
public class Heap{
public ArrayList<Integer> heapArray = null;
public Heap (Integer data) {
heapArray = new ArrayList<Integer>();
heapArray.add(null);
heapArray.add(data);
}
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)){
return true;
} else {
return false;
}
}
public boolean insert(Integer data){
if(heapArray == null){
heapArray = new ArrayList<Integer>();
heapArray.add(null);
heapArray.add(data);
}else{
this.heapArray.add(data);
inserted_idx = this.heapArray.size()-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 Integer pop(){
if(this.heapArray == null){return null;}
else{
return this.heapArray.get(1);
}
}
}
Java
복사
힙 클래스 구현4 - delete2
◦
상단의 데이터 삭제 시, 가장 최하단부 왼쪽에 위치한 노드(일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동
◦
root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함(swap)
public class Heap{
public ArrayList<Integer> heapArray = null;
public Heap (Integer data) {
heapArray = new ArrayList<Integer>();
heapArray.add(null);
heapArray.add(data);
}
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)){
return true;
} else {
return false;
}
}
public boolean move_down(Integer popped_idx){
Integer left_child_popped_idx, right_child_popped_idx;
left_child_popped_idx = popped_idx * 2;
right_child_popped_idx = popped_idx * 2 + 1;
if(left_child_pop.idx>=this.heapArray.size()){
return false;
}else if (right_child_popped_idx>=this.heapArray.size()){
if(this.heapArray.get(popped_idx)<this.heapArray.get(left_child_popped_idx)){
public boolean insert(Integer data){
if(heapArray == null){
heapArray = new ArrayList<Integer>();
heapArray.add(null);
heapArray.add(data);
}else{
this.heapArray.add(data);
inserted_idx = this.heapArray.size()-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 Integer pop(){
if(this.heapArray == null){return null;}
else{
return this.heapArray.get(1);
}
}
}
Java
복사