[DataStructure&Algorithm] Heap, 힙

2024. 4. 21. 19:09· 자료구조&알고리즘
목차
  1. 개요 - Heap이란?
  2. 특징
  3. 데이터 삽입
  4. 데이터 삭제
  5.  
  6.  
  7. 응용
728x90
반응형

 

Heap


개요 - Heap이란?

Heap이란 Heap Tree 구조를 가지며, 여러 개의 값중에서, 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 이진트리 구조이다.

 

heap이라는 영단어 자체가 '어떤 것을 차곡차곡 쌓아올린 더미'라는 뜻이다. 이러한 이유로, 힙은 항상 완전 이진 트리 구조를 띄어야하며, 부모 노드의 값은 자식 노드의 값보다 기준에 따라 크거나, 작아야한다. 만약 큰 경우라면 root노드, 즉 최상단 부모 노드는 해당 배열에서의 최대 값을 가질 것이고, 작은 경우라면 반대로 최솟값을 가질 것이다. 이를 모두 Max Heap(최대 힙), Min Heap(최소 힙)이라고 한다.

 

이러한 구조적인 특징상, 최대 값이나 최소 값을 찾는데 매우 빠른 속도를 자랑한다.


특징

  • 완전 이진 트리 구조를 지닌다.
  • 데이터 삽입과 삭제 모든 O(logN)의 복잡도를 가진다.
    • 구조상, 한 층이 늘어날 수록 노드 수가 2배가 되기 때문이다.
  • 비선형 자료구조이다.

데이터 삽입

  1. 가장 마지막 노드쪽에 데이터를 삽입한다.
  2. 부모 노드와 값을 비교한다.
  3. 부모 노드와 값을 swap한다.
    1. 최대 힙인 경우, 자식 노드가 부모 노드보다 값이 큰 경우, 부모 노드와 값을 swap한다.
    2. 최소 힙인 경우, 자식 노드가 부모 노드보다 값이 작은 경우, 부모 노드와 값을 swap한다.
  4.  힙의 규칙에 맞을 때까지 3의 과정을 반복한다.

힙 데이터 삽입 순서

데이터 삭제

힙 자료구조에서 데이터 삭제는 무조건 root 노드만 삭제한다.

  1. 루트 노드를 제거한다.
  2. 루트 자리에 마지막 인덱스에 저장된 값을 저장한다.(스왑)
  3. 새로운 루트 노드와 자식 노드들을 비교한다.
  4. 조건에 만족하면, 그대로 두고 그렇지 않다면, 스왑을 진행한다.
    1. 최대힙
      1. 부모보다 더 큰 자식이 없다면, 스왑하지 않고 종료.
      2. 하나 존재한다면, 해당 노드와 스왑
      3. 둘 존재한다면, 그 중 큰 노드와 부모노드 스왑.
    2. 최소힙
      1. 부모보다 더 큰 자식이 없다면, 스왑하지 않고 종료.
      2. 하나 존재한다면, 해당 노드와 스왑
      3. 둘 존재한다면, 그 중 큰 노드와 부모노드 스왑.
  5. 조건을 만족할 때까지 반복한다.

 

 


응용

  • 우선 순위 큐를 구현하는데 사용된다.
  • 힙 정렬을 구현할 수 있다.
728x90
반응형
저작자표시 (새창열림)

'자료구조&알고리즘' 카테고리의 다른 글

[DataStructure&Algorithm] BFS, 너비 우선 탐색  (0) 2024.04.29
[DataStructure&Algorithm] DFS, 깊이 우선 탐색  (0) 2024.04.29
[DataStructure&Algorithm] LinkedList  (1) 2024.04.19
[DataStructure&Algorithm] HashMap  (1) 2024.04.19
[DataStructure&Algorithm] Array  (0) 2024.04.19
  1. 개요 - Heap이란?
  2. 특징
  3. 데이터 삽입
  4. 데이터 삭제
  5.  
  6.  
  7. 응용
'자료구조&알고리즘' 카테고리의 다른 글
  • [DataStructure&Algorithm] BFS, 너비 우선 탐색
  • [DataStructure&Algorithm] DFS, 깊이 우선 탐색
  • [DataStructure&Algorithm] LinkedList
  • [DataStructure&Algorithm] HashMap
heesang0930
heesang0930
백엔드 개발자로 성공하고 싶은 사람의 블로그
반응형
250x250
heesang0930
Tech Blog
heesang0930
전체
오늘
어제
07-01 05:02
  • 분류 전체보기
    • 책
    • Lang
    • Backend
      • Framework
      • Deployment
    • Cloud
    • 데이터베이스
    • Architecture
      • Monitoring
    • CS
    • 코딩 테스트
    • 자료구조&알고리즘
    • etc..
    • 공부

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • GitHub
  • Medium
  • will-post list

공지사항

  • 신입 백엔드개발자

인기 글

hELLO · Designed By 정상우.v4.2.2
heesang0930
[DataStructure&Algorithm] Heap, 힙
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.