히프 (Heap)

혁콩·2022년 11월 11일

자료구조 알고리즘

1. Intro

히프(Heap)란 완전 이진트리이면서 각 조건을 만족한다

최대 히프(max heap) : 각 노드의 키값이 자식의 키값보다 작지 않음

최소 히프(min heap) : 각 노드의 키값이 자식의 키값보다 크지 않음

여기선 최대 히프(max heap)으로 구현해보도록 하겠다.

2. Contents

최대 히프의 경우 트리의 가장 큰 값을 찾아내기 쉽다. 회대 히프는 항상 루트노드의 값이 가장 큰 값이기 때문이다.

이 때문에

삽입 연산 시 적절한 위치를 찾아 삽입

삭제 연산 시 가장 큰 값(루트노드)를 반환하고 히프를 재구성

해야 한다.

히프는

이진트리의 한 종류이기 때문에 Node를 통한 연결리스트로도 구현할 수 있지만 배열을 통해서도 구현할 수 있다.

배열로 구현 시 주소값을 직접 계산할 수 있어 한번에 원하는 노드로 접근이 가능하여 연산을 더욱 빠르게 할 수 있다.

아래에서는 배열을 통한 최대 히프의 구현, 삽입과 삭제 연산에 대해 알아보겠다.

3. Heap의 구조와 연산

3.1. 기본구조 :

히프는 배열로 구성되기 때문에 멤버로 값의 개수, 히프의 크기와 키값을 입력받을 배열을 준비해준다.

class Heap {
	private int count;
	private int size;
	private int[] itemArray;

	public Heap() {
		count = 0;
		size = 64;
		itemArray = new int[size];
	}
}

힙이 아닌 배열을 힙으로 바꿔 초기화해주는 생성자를 구현해보았다.
배열을 돌면서 하나씩 insert 해주어도 최대히프는 유지되지만, 이렇게 해보았다!

public Heap(int[] origArray) {
	// 힙이 아닌 배열을 힙으로 바꿔 초기화
	this();
	int n = origArray.length-1;
	count = n;
	for(int i=n/2;i>=1;i--) {
		int p = i;
		for(int j = 2*p;j<=n;j=2*j) {
			if(j < n) {
				if(origArray[j] < origArray[j+1]) {
					j++;
				}
			}
			if(origArray[p] >= origArray[j]) { 
				break;
			}
			int temp = origArray[p];
			origArray[p] = origArray[j];
			origArray[j] = temp;
			p = j;
		}
	}
	for(int i=1;i<origArray.length;i++) {
		itemArray[i] = origArray[i];
	}
}

3.2. 삽입 :

삽입 시 마지막 인덱스(count)부터 시작해 부모와 비교, 더 크다면 부모를 한 레벨 아래로 내리고, 제 자리를 찾으면 그 자리에 새로운 값을 삽입한다.

public void insert(int newItem) {
	// 추가
	count++;
	int i = count;
	while(true) {
		if(i == 1) break;
		if(newItem <= itemArray[i/2]) break; // 삽입할 값이 부모보다 작을 때
		itemArray[i] = itemArray[i/2]; // 아니라면 부모의 값을 현재노드로 내림
		i = i/2; // 포인터를 부모로 이동
	}
	itemArray[i] = newItem; // 찾은 자리에 새로운 값 삽입
}

3.3. 삭제 :

삭제연산은 가장 큰 값(루트)을 반환하며, 그에 따른 히프의 재구성이 필요하다.

public int delete() {
	// 삭제
	if(count == 0) return -1; // 히프가 비었으면 -1 반환
	int item = itemArray[1]; // 루트 값 저장
	int temp = itemArray[count];
	count--;
		
	int i = 1;
	int j = 2;
	
	while(j <= count) {
		if(itemArray[j] < itemArray[j+1]) { // 두 노드중 큰 노드로 이동
			j++;
		}
		if(temp >= itemArray[j]) { // 가장 끝값이 현재 위치보다 크면 탈출
			break;
		}
		itemArray[i] = itemArray[j]; 
		i = j;
		j = j*2; // 현재위치 이동
	}
	itemArray[i] = temp;
	return item; // 저장한 루트값 반환
}