[자료구조] 힙이란?(heap)

[자료구조] 힙이란?(heap)

728x90

힙이란?

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

키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는 느슨한 정렬상태.

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

중복값을 허용한다.(이진 탐색트리와는 다름.)

우선순위 큐, 허프만정렬, 힙정렬 등에서 사용

힙의 종류

1. 최대힙(Max heap)

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

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

2. 최소힙(Min heap)

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

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

-> 완전 이진트리 : 마지막 레벨을 제외하곤 완전히 꽉 찬 상태이고, 마지막 레벨의 맨 왼쪽부터 꽉 차 있어야함.

힙의 구현

힙은 논리적 자료구조로 물리적으로는 보통 배열을 이용해 구현

구현 편의를 위해 배열의 0번인덱스는 비워둠

힙의 삽입은 힙 정렬(heap sorting), 힙의 삭제는 heapify를 사용함.

힙의 표현 루트노드 A[1] A[i]의 부모노드 A[i/2] A[i]의 왼쪽노드 A[2i] A[i]의 오른쪽노드 A[2i + 1]

heapify

트리의 전체모양은 완전 이진트리.

왼쪽, 오른쪽 부트리는 완전 그 자체로 힙

유일하게 root만이 힙이 아닐 때

max heapify와 min heapify는 부호만 반대로

max heapify

1. 루트를 기준으로 자식노드중 큰 값과 자리를 바꿈.(없을경우 왼쪽,오른쪽의 부트리는 힙이기 때문에 정렬완료.)

2. 자리를 바꾼 방향의 부트리에서 자리 변경이 안 일어 날 때 까지 1번을 반복함.

힙정렬

배열을 힙을 만들기 위해 힙정렬을 함.

배열<->트리 논리적 구조로 생각하여 배열을 완전이진트리로 만든다

맨 마지막 리프노드의 부트리부터 heapify진행.(그림의 7을 루트노드 16부터 진행)

힙의 삽입

힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.

새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.(힙정렬 참조)

힙의 삭제

힙의 루트와 맨 마지막값을 바꿈.

힙의 크기를 1줄인다.

힙의 루트로 heapify진행.

728x90

from http://shutcoding.tistory.com/75 by ccl(A) rewrite - 2021-09-21 20:01:04