[자료구조] 2023_1106 힙

11/06 자료구조 스터디

---

[07]
1. 힙(Heap) 이란?
2. 힙의 기본 동작
3. 힙의 여러가지 종류
4. 힙 활용문제 풀어보기

[힙(Heap) 이란?]

최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한 자료구조이다. 또한 힙 트리에서는 중복된 값을 허용한다.

[힙의 기본 동작]

삽입 : 최하단부에 삽입하며 최대 힙일 경우 부모노드보다 자식노드가 더 크면 위치를 서로 바꾼다. 최소 힙도 마찬가지로 부모노드가 자식노드보다 더 크면 위치를 서로 바꾼다.
삭제 : 최대값 혹은 최소값이 부모노드가 삭제 되고 가장 최하단부의 노드값을 루트로 옮긴다. 이때 자식노드와 비교하여 최대 힙일 때 루트가 더 작으면 자식노드와 바꾼다

[힙의 여러가지 종류]

최대 힙(max heap)	최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리	부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
부모 노드>=자식노드	부모노드<=자식노드

[힙 활용문제 풀어보기]

빼내기 전	빼낸 후

최소 힙에서 값을 빼내오는 작업을 하고 있다. root에(가장 작은 값) 값이 없어졌는데 루트 밑의 노드들 중에서 어떤 값을 root에 넣어야 할까?
1.2
2.3
3.4
4.5
5.6