[알고리즘 위한 한발짝 두발짝🐾] 힙(heap) 자료구조

<본 블로그는 코딩문 codingmoon 님의 유튜브를 참고해서 공부하며 작성하였습니다 :-)>

=> 힙(heap) 자료구조 개념 이해하기 | 개발자 코딩테스트 & 면접 지식

 

🫧 힙(heap) 자료구조

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

: A가 B의 부모 노드이면, A의 키 값과 B의 키 값 사이에는 대소 관계가 성립된다

- 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 가짐

left : i * 2 + 1
right : i * 2 + 2
parent : (i - 1) / 2

- 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙 가짐

 

🫧 힙(heap) 주요 메서드

peek() : 최대/최소값 리턴

size() : 힙 사이즈 리턴

isEmpty() : 힙 사이즈 0 체크 

🚀 코테 문제
- k번째 큰 수
- 가장 빈번하게 나오는 수 /글자 k개
- 출현 빈도별로 문자 정렬
- 이중 우선 순위