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

[자료구조-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 heap; // 1. 생성자 public Heap() { heap = new ArrayList(); 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 heap; // 1. 생성자 public Heap() { heap = new ArrayList(); 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] } }

from http://ju-zero.tistory.com/74 by ccl(A) rewrite - 2021-10-13 17:00:32