[자료구조] 자바 에서의 힙(Heap) #1

힙(Heap) 이란?

- 힙 : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

    - 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

* 힙을 사용하는 이유?

- 단순히 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸린다.

- 이에 반해, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(log n) 이 걸린다.

- 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다.

 

힙(Heap) 구조

- 힙은 최대값을 구하기 위한 구조(최대 힙 - Max Heap) 와 최소값을 구하기 위한 구조(최소 힙 - Min Heap) 로 분류할 수 있다.

- 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조이다.

1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다.(최대 힙의 경우)

    * 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같음

2. 완전 이진 트리형태를 가진다.

 

* 힙과 이진 탐색 트리의 공통점과 차이점

- 공통점 :

    * 힙과 이진 탐색 트리는 모두 이진 트리이다.

- 차이점 :

    * 힙은 각 노드의 값이 자식 노드보다 크거나 같다.(최대 힙의 경우)

    * 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 크다.

       (힙 과는 달리 오른쪽 자식 노드가 부모 노드보다 크거나 같다.)

    * 힙은 이진 탐색 트리의 조건인 자식 노드중 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건이 없다.

        ** 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있다.

        ** 어쨌든 부모 노드보다는 작거나 같다. - 최대 힙의 경우

- 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 된다.

 

 

힙에 데이터 삽입하기(최대 힙의 경우)

-  힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입된다.

-> 최하단 왼쪽 노드부터 시작하여, 트리에서 해당 Level 에 노드들이 다 채워지고 나면 그 다음 Level 로 이동해서 가장 왼쪽 부터 다시 데이터를 삽입하는 구조

 

힙에 데이터 삽입하기 - 삽입할 데이터가 힙의 데이터 보다 클 경우(최대 힙)

- 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞춰, 최하단부 왼쪽 노드부터 채워진다.

- 채워진 노드 위치에서 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복해준다.

- 부모 노드와 위치를 바꿔주는 작업을 반복하다가 만약 삽입된 데이터가 트리에서 최대값에 해당 할 경우, 결국 결과적으로 해당 노드는 트리의 Root Node 가 된다.

 

 

힙의 데이터 삭제하기(최대 힙의 경우)

- 보통 삭제는 최상단 노드(Root Node) 를 삭제하는 것이 일반적이다.

    * 힙의 용도는 최대값 또는 최소값을 Root Node 에 놓고, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것이다.

    * 힙에서 최대값이나 최소값이 아닌 다른 노드를 삭제하는 경우는 거의 없다고 봐도 무방하다.

- 상단의 데이터 삭제 시, 일반적으로 가장 마지막에 추가한 노드를 Root Node 로 이동시킨다.

- Root Node 의 값이 Child Node 보다 작을 경우, Root Node 의 Child Node 중 가장 큰 값을 가진 노드와 Root Node 의 위치를 바꿔주는 작업을 반복한다.

 

 

힙을 직접 구현해보자.

- 일반적으로 힙 구현 시 배열, 또는 리스트 자료구조를 활용할 수 있다.

- 위와 같은 자료구조가 가능한 이유는 힙이 완전 이진 트리의 구조를 띄기 때문이다.

- 배열과 리스트는 인덱스가 0번 부터 시작하지만, 힙 구현의 편의를 위해 Root Node 인덱스 번호를 1로 지정하면 구현이 좀 더 쉬워진다.

    * 부모 노드 인덱스 번호(Parent node's index) = 자식 노드 인덱스 번호(Child node's index) / 2(파이썬의 경우 // - 파이썬에서 / 기호를 하나만 사용할 경우 숫자에 따라 실수 형태의 몫이 나오게 된다.)

    * 왼쪽 자식 노드 인덱스 번호(Left Child node's index) = 부모 노드 인덱스 번호(Parent node's index) * 2

    * 오른쪽 자식 노드 인덱스 번호(Right Child node's index) = 부모 노드 인덱스 번호(Parent node's index) * 2 + 1

    * 위와 같이 인덱스 번호를 통해 각 인덱스에 어떤 노드가 있는지 구분할 수 있다.

 

* 우선 각 노드의 객체 클래스를 만들어준다.

- Heap.java

public class Heap {
private List<Integer> heapArray;
	
	public Heap(int data) {
		this.heapArray = new ArrayList<Integer>();
		this.heapArray.add(null);
		this.heapArray.add(data);
	}
    
    // ...이하 코드 생략
}

- 생성자를 통해 객체를 생성할 때 heapArray 필드에 ArrayList 타입의 객체를 참조값으로서 적재해준다.

- 리스트의 0번째 인덱스를 null 로 초기화해준다.

- 리스트의 1번째 인덱스에 입력받은 data 변수를 추가해준다.(Root Node 생성)

 

* 다음은 객체 생성자 코드를 포함한 전체 코드이다.

public class Heap {
	private List<Integer> heapArray;
	
	public Heap(int data) {
		this.heapArray = new ArrayList<Integer>();
		this.heapArray.add(null);
		this.heapArray.add(data);
	}
	
	public boolean insert(int data) {

		if(this.heapArray.size() == 0) {
			this.heapArray.add(null);
			this.heapArray.add(data);
			
			return true;
		}
		
		this.heapArray.add(data);
		
		int insertedIdx = this.heapArray.size() - 1; 
		while(moveUp(insertedIdx)) {
        
			int parentIdx = insertedIdx / 2;
			
			int temp = this.heapArray.get(insertedIdx);
			this.heapArray.set(insertedIdx, this.heapArray.get(parentIdx));
			this.heapArray.set(parentIdx, temp);
			
			insertedIdx = parentIdx;
		}
		return true;
	}
	
	private boolean moveUp(int insertedIdx) {
    
		if(insertedIdx <= 1) 
			return false;
		
		int parentIdx = insertedIdx / 2;

		if(this.heapArray.get(insertedIdx) > this.heapArray.get(parentIdx)) {
			return true;
		}
		else
			return false;
	}
	
	public int pop() {
		
		int returnedData = this.heapArray.get(1);
		this.heapArray.set(1, this.heapArray.get(this.heapArray.size()-1));
		this.heapArray.remove(this.heapArray.size()-1);

		int popedIdx = 1;
		
		while(moveDown(popedIdx)) {
			int leftChildIdx = popedIdx * 2;
			int rightChildIdx = popedIdx * 2 + 1;

			if(rightChildIdx >= this.heapArray.size()) {
				if(this.heapArray.get(popedIdx) < this.heapArray.get(leftChildIdx)) {
					int temp = this.heapArray.get(leftChildIdx);
					this.heapArray.set(leftChildIdx, this.heapArray.get(popedIdx));
					this.heapArray.set(popedIdx, temp);
					
					popedIdx = leftChildIdx;
				}
			}
			else {
				if(this.heapArray.get(leftChildIdx) > this.heapArray.get(rightChildIdx)) {
					if(this.heapArray.get(popedIdx) < this.heapArray.get(leftChildIdx)) {
						int temp = this.heapArray.get(leftChildIdx);
						this.heapArray.set(leftChildIdx, this.heapArray.get(popedIdx));
						this.heapArray.set(popedIdx, temp);
						
						popedIdx = leftChildIdx;
					}
				}
				else {
					if(this.heapArray.get(popedIdx) < this.heapArray.get(rightChildIdx)) {
						int temp = this.heapArray.get(rightChildIdx);
						this.heapArray.set(rightChildIdx, this.heapArray.get(popedIdx));
						this.heapArray.set(popedIdx, temp);
						
						popedIdx = rightChildIdx;
					}
				}
			}
		}
		
		return returnedData;
	}

	private boolean moveDown(int popedIdx) {
		
		int leftChildIndex = popedIdx * 2;
		int rightChildIndex = popedIdx * 2 + 1;
		
		if(leftChildIndex >= this.heapArray.size())
			return false;
		
		else if(rightChildIndex >= this.heapArray.size()) {
			if(this.heapArray.get(popedIdx) < this.heapArray.get(leftChildIndex))
				return true;
			else
				return false;
		}
		
		else {
			if(this.heapArray.get(leftChildIndex) > this.heapArray.get(rightChildIndex)) {
				if(this.heapArray.get(popedIdx) < this.heapArray.get(leftChildIndex))
					return true;
				else
					return false;
			}
			else {
				if(this.heapArray.get(popedIdx) < this.heapArray.get(rightChildIndex))
					return true;
				else
					return false;
			}
		}
	}

	public List<Integer> getHeapArray() {
		return heapArray;
	}
}

 

데이터의 삽입과 삭제 코드에 대해서는 다음 글에서 자세히 알아보자.