[자료 구조] Heap의 개념 설명과 구현

⬛ 사전 지식

 

1. 완전 이진 트리

• 각 노드가 최대 2개의 자식 노드를 갖는 이진 트리 중 왼쪽부터 차례대로 채워져 있는 트리
• 최하단 레벨의 노드는 좌측부터 채워져 있어야 한다.

2. 우선순위 큐

• 우선순위가 높은 데이터가 먼저 나가는 형태의 큐
• 모든 항목은 우선순위를 가지며 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 큐에서 삭제
• 우선순위 큐의 구현 방법
  1. 배열로 구현할 경우 우선순위를 비교하는 연산이 필요하기 때문에 최대 O(N)의 시간 복잡도를 가진다.
  2. 연결리스트로 구현할 경우에도 노드간의 연결을 거쳐 우선순위를 비교하는 연산이 필요하기 때문에 최대 O(N)의 시간 복잡도를 가진다.
  3. 완전 이진트리인 힙으로 구현할 경우 최대 O(logN)의 시간 복잡도를 가진다.

  

⬛ Heap의 개념

• 우선순위 큐를 구현하기 위해 고안
• 완전 이진 트리 구조로 최댓값 및 최솟값을 빠르게 찾아낼 수 있는 자료구조
• Heap은 이진 트리 구조를 배열에 저장한 것이기 때문에 반정렬 상태이다. 배열만 보았을 때는 정렬되어 있는 상태가 아니다.

⬛ Heap의 종류

1. 최대 힙(max Heap)

• 숫자가 클수록 우선순위가 높은 경우 - 가장 큰 값이 Root노드의 키 값
• 부모 노드의 키 값 ≥ 자식 노드의 키 값인 완전 이진 트리

2. 최소 힙(min Heap)

• 숫자가 작을수록 우선순위가 높은 경우 - 가장 작은 값이 Root노드의 키 값
• 부모 노드의 키 값 ≤ 자식 노드의 키 값인 완전 이진 트리

⬛ Heap을 구현하기 앞서..

• Heap은 보통 배열로 구현하며 구현을 쉽게 하기 위해 첫번째 인덱스인 0은 사용하지 않는다.
• 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
• 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
• 부모 노드의 인덱스 = 자식 노드의 인덱스 / 2
• Heapify(재구조화) : 요소를 삽입하거나 삭제할 때 힙의 조건을 다시 맞춰주기 위해 노드의 위치를 바꾸는 과정

⬛ Heap의 삽입

1. 새로운 노드를 완전 이진 트리 구조를 유지하며 힙의 마지막 노드에 삽입
2. 추가된 노드의 값과 부모의 노드의 값과 비교하여 교환
3. 최대 힙 또는 최소 힙의 조건을 만족할 때까지 교환을 반복

2, 3번이 상향 Heapify 과정이며 삽입 연산의 Heapify 과정은 최악의 경우 O(logN)의 시간 복잡도를 가진다.

 

• 최대 힙의 삽입 과정

  

⬛ Heap의 삭제

1. 우선 순위 큐이기 때문에 최대 힙과 최소 힙 둘다 루트 노드(최대 힙에서는 가장 큰 값이, 최소 힙에서는 가장 작은 값)를 삭제
2. 가장 말단에 있는 노드를 루트로 이동
3. 루트 노드의 값부터 자식 노드의 값을 비교하여 교환 (최대 힙에서는 더 큰 값을 가진 자식 노드와, 최소 힙에서는 더 작은 값을 가진 자식 노드와 교환)
4. 최대 힙 또는 최소 힙의 조건을 만족할 때까지 비교를 반복

2, 3, 4번이 하향 Heapify 과정이며 삭제 연산의 Heapify 과정은 최악의 경우 O(logN)의 시간 복잡도를 가진다.

 

• 최대 힙의 삭제 과정

⬛ Heap 구현

MyMaxHeap.java

package com.heap;

public class MyMaxHeap {
	private int heap[];
	private int size = 0;

	public MyMaxHeap(int heapSize) {
		heap = new int[heapSize + 1];
	}

	private void insert(int data) {
		if (isFull()) {
			System.out.println("heap is full");
		} else {
			heap[++size] = data;
			for (int i = size; i > 1; i = i / 2) { // 부모 노드의 인덱스 = 자식 노드의 인덱스 /2
				int temp;
				if (heap[i] > heap[i / 2]) {
					temp = heap[i / 2];
					heap[i / 2] = heap[i];
					heap[i] = temp;
				} else {
					break;
				}
			}
		}
	}

	private int delete() {
		if (isEmpty()) {
			System.out.print("no item ");
			return -1;
		}
		int data = heap[1];
		heap[1] = heap[size--];
		int temp;

		for (int i = 1; i * 2 <= size;) {
			if (heap[i * 2] > heap[i] && heap[i * 2] > heap[i * 2 + 1]) { // 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
				temp = heap[i * 2]; // 오른쪽 자식 노드의 인덱스 = 부모 노드의* 2 + 1
				heap[i * 2] = heap[i];
				heap[i] = temp;
				i = i * 2;
			} else if (heap[i * 2 + 1] > heap[i] && heap[i * 2 + 1] > heap[i * 2]) {
				temp = heap[i * 2 + 1];
				heap[i * 2 + 1] = heap[i];
				heap[i] = temp;
				i = i * 2 + 1;
			} else {
				break;
			}
		}

		return data;
	}

	private boolean isEmpty() {
		if (size == 0) {
			return true;
		} else {
			return false;
		}
	}

	private boolean isFull() {
		if (size == heap.length - 1) {
			return true;
		} else {
			return false;
		}
	}

	@Override
	public String toString() {
		String str = "[";
		for (int i = 1; i < size; i++) {
			str += heap[i];
			str += ", ";
		}
		str += heap[size];
		str += "]";
		return str;
	}

	public static void main(String[] args) {
		MyMaxHeap mmh = new MyMaxHeap(10);
		mmh.insert(1);
		mmh.insert(2);
		mmh.insert(6);
		mmh.insert(4);
		mmh.insert(5);
		mmh.insert(3);
		mmh.insert(7);
		mmh.insert(9);
		mmh.insert(10);
		mmh.insert(8);
		System.out.println(mmh);
		System.out.println(mmh.delete());
		System.out.println(mmh.delete());
		System.out.println(mmh.delete());
		System.out.println(mmh);
	}

}

 

MyMinHeap.java

package com.heap;

public class MyMinHeap {
	private int heap[];
	private int size = 0;

	public MyMinHeap(int heapSize) {
		heap = new int[heapSize + 1];
	}

	private void insert(int data) {
		if (isFull()) {
			System.out.println("heap is full");
		} else {
			heap[++size] = data;
			for (int i = size; i > 1; i = i / 2) { // 부모 노드의 인덱스 = 자식 노드의 인덱스 /2
				int temp;
				if (heap[i] < heap[i / 2]) {
					temp = heap[i / 2];
					heap[i / 2] = heap[i];
					heap[i] = temp;
				} else {
					break;
				}
			}
		}
	}

	private int delete() {
		if (isEmpty()) {
			System.out.print("no item ");
			return -1;
		}
		int data = heap[1];
		heap[1] = heap[size--];
		int temp;
		for (int i = 1; i * 2 <= size;) { // 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
			if (heap[i * 2] < heap[i] && heap[i * 2] < heap[i * 2 + 1]) { // 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
				temp = heap[i * 2];
				heap[i * 2] = heap[i];
				heap[i] = temp;
				i = i * 2;
			} else if (heap[i * 2 + 1] < heap[i] && heap[i * 2 + 1] < heap[i * 2]) {
				temp = heap[i * 2 + 1];
				heap[i * 2 + 1] = heap[i];
				heap[i] = temp;
				i = i * 2 + 1;
			} else {
				break;
			}
		}

		return data;
	}

	private boolean isEmpty() {
		if (size == 0) {
			return true;
		} else {
			return false;
		}
	}

	private boolean isFull() {
		if (size == heap.length - 1) {
			return true;
		} else {
			return false;
		}
	}

	@Override
	public String toString() {
		String str = "[";
		for (int i = 1; i < size; i++) {
			str += heap[i];
			str += ", ";
		}
		str += heap[size];
		str += "]";
		return str;
	}

	public static void main(String[] args) {
		MyMinHeap mmh = new MyMinHeap(10);
		mmh.insert(8);
		mmh.insert(7);
		mmh.insert(6);
		mmh.insert(9);
		mmh.insert(4);
		mmh.insert(3);
		mmh.insert(5);
		mmh.insert(2);
		mmh.insert(1);
		mmh.insert(10);
		System.out.println(mmh);
		System.out.println(mmh.delete());
		System.out.println(mmh);
		System.out.println(mmh.delete());
		System.out.println(mmh);
		System.out.println(mmh.delete());
		System.out.println(mmh);
	}

}