자료구조

[자료구조] 힙(Heap)

1. 정의 🐳 힙(Heap)이란 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다. 힙의 특징 완전 이진트리의 일종이다. 반정렬 상태이다. 최대힙(Max Heap) 또는 최소힙(Min Heap)에 따라서 루트 노드가 항상 가장 큰 값이거나 가장 작은 값을 유지하기 때문이다. 중복된 값을 허용한다. 힙의 종류 최대 힙 (Max Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 형식 최소 힙 (Min Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 형식 2. 동작 방식 🐟 인덱스 0 1 2 3 4 5 6 7 8 값 - 9 7 6 4 5 1 3 8 Heap은 배열을 통해 쉽게 구현이 가능하다. 그 이유는 힙이 완전 이진트리이..