[자료구조-05] 힙(Heap)

1. 힙(Heap)이란?

- 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조

 

출처 : https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

 

- A가 B의 부모노드(parent node)이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립함

- 단, 형제 사이에는 대소관계가 성립하지 않음

- 일종의 반정렬 상태(느슨한 정렬 상태) 유지

- 대부분은 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용

- 중복 허용

힙(Heap) vs 이진 탐색 트리(Binary Search Tree)
- 힙은 중복된 값을 허용함
- 이진 탐색 트리는 중복된 값을 허용하지 않음

 

- 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드에 위치

- 우선순위 큐와 같은 추상적인 자료형 구현 가능

우선순위 큐(Priority Queue) : 가장 우선순위가 높은 데이터
- 배열, 연결리스트, 힙으로 구현 가능
- 힙으로 구현하는 것이 가장 효율적

 

2. 이진 힙(Binary Heap)

- 노드의 값이 특정한 순서를 가지고 있는 완전 이진 트리

- 마지막 레벨을 제외하고 모든 이진 트리의 레벨이 노드로 채워져 있음

 

 

3. 힙의 종류

 

 

1) 최대 힙(Max Heap)

- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같은 완전 이진 트리

- key(부모 노드) >= key(자식 노드)

 

2) 최소 힙(Min Heap)

- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같은 완전 이진 트리

- key(부모 노드) <= key(자식 노드)

 

 

4. 힙의 구현

1) 자료구조

- 힙을 저장하는 표준적인 자료구조는 배열

- 구현의 용이성을 위해 배열의 첫 번째 인덱스 0은 사용하지 않음

- 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음

 

2) 부모 노드와 자식 노드의 관계

- 왼쪽 자식의 인덱스 = (부모 인덱스) * 2

- 오른쪽 자식의 인덱스 = (부모 인덱스) * 2 + 1

- 부모의 인덱스 = (자식 인덱스) / 2

 

-> 본 게시글에선 Min Heap을 구현해보고자 함

 

5. Heap 클래스 및 생성자 구성

public class Heap {

	private ArrayList<Integer> heap;

	// 1. 생성자
	public Heap() {
		heap = new ArrayList<Integer>();
		heap.add(0); // 0번째 인덱스 사용 X
	}

 

6. 삽입(insert)

	// 2. 삽입
	public void insert(int val) {
		heap.add(val);
		int idx = heap.size() - 1;
		while (idx > 1 && heap.get(idx / 2) > heap.get(idx)) { // 1) 루트 도달 2) 부모보다 작음 시 반복문 종료
			swap(idx, idx / 2); // 현재 노드와 부모 노드 바꾸기

			idx /= 2; // 부모 노드 인덱스 값으로 변경
		}
	}

 

7. 삭제(delete)

	// 3. 삭제
	public int delete() {
		if (heap.size() - 1 < 1) {
			return 0;
		}

		int item = heap.get(1); // 루트 노드 꺼내기

		swap(1, heap.size() - 1); // 현재 노드와 루트 노드 바꾸기

		int idx = 1;
		while ((idx * 2) < heap.size()) {
			int min = heap.get(idx * 2); // 왼쪽 자식 노드
			int minPos = idx * 2;

			if ((idx * 2 + 1) < heap.size() && min > heap.get(idx * 2 + 1)) { // 오른쪽 자식 노드가 있고 왼쪽 자식 노드보다 작을 때
				min = heap.get(idx * 2 + 1);
				minPos = idx * 2 + 1;
			}
			
			if(min > heap.get(idx))	// 부모 노드가 더 작으면 반복문 종료
				break;
			
			swap(idx, minPos);
			idx = minPos;
			
		}

 

8. 전체 코드

import java.util.ArrayList;

public class Heap {

	private ArrayList<Integer> heap;

	// 1. 생성자
	public Heap() {
		heap = new ArrayList<Integer>();
		heap.add(0); // 0번째 인덱스 사용 X
	}

	// 2. 삽입
	public void insert(int val) {
		heap.add(val);
		int idx = heap.size() - 1;
		while (idx > 1 && heap.get(idx / 2) > heap.get(idx)) { // 1) 루트 도달 2) 부모보다 작음 시 반복문 종료
			swap(idx, idx / 2); // 현재 노드와 부모 노드 바꾸기

			idx /= 2; // 부모 노드 인덱스 값으로 변경
		}
	}

	// 3. 삭제
	public int delete() {
		if (heap.size() - 1 < 1) {
			return 0;
		}

		int item = heap.get(1); // 루트 노드 꺼내기

		swap(1, heap.size() - 1); // 현재 노드와 루트 노드 바꾸기
		heap.remove(heap.size() - 1);
		
		int idx = 1;
		while ((idx * 2) < heap.size()) {
			int min = heap.get(idx * 2); // 왼쪽 자식 노드
			int minPos = idx * 2;

			if ((idx * 2 + 1) < heap.size() && min > heap.get(idx * 2 + 1)) { // 오른쪽 자식 노드가 있고 왼쪽 자식 노드보다 작을 때
				min = heap.get(idx * 2 + 1);
				minPos = idx * 2 + 1;
			}
			
			if(min > heap.get(idx))	// 부모 노드가 더 작으면 반복문 종료
				break;
			
			swap(idx, minPos);
			idx = minPos;
			
		}

		return item;
	}

	public void swap(int idx1, int idx2) {
		int tmp = heap.get(idx1);
		heap.set(idx1, heap.get(idx2));
		heap.set(idx2, tmp);
	}
	
	@Override
	public String toString() {
		return heap.toString();
	}

	public static void main(String[] args) {
		Heap minHeap = new Heap();
		
		int[] arr = {1, 3, 9, 5, 4, 2};
		for(int i = 0; i < arr.length; i++) {
			minHeap.insert(arr[i]);
		}
		
		System.out.println(minHeap.toString());	// [0, 1, 3, 2, 5, 4, 9]
		
		int deleteItem = minHeap.delete();
		System.out.println("deleteItem: " + deleteItem);
		System.out.println(minHeap.toString());	// [0, 2, 3, 9, 5, 4]
		
		int deleteItem2 = minHeap.delete();
		System.out.println("deleteItem: " + deleteItem2);
		System.out.println(minHeap.toString());	// [0, 3, 4, 9, 5]
		
	}
}