min heap1 [자료구조] 힙 (Heap) C/C++ 구현 - 알고리즘 // 최소 힙, 최대 힙 요즘 heap (min heap, max heap) 관련 과제 요청이 많이 들어와서 힙 자료구조에 대해 글을 써봅니다. 힙은 이진트리 (Binary Tree)로 구성할 수 있으며 트리 구조체로 구현하거나 또는 1차원 배열로 쉽게 구현할 수 있습니다. 구현 시 하나의 규칙만 지켜주면 되는데 최소 힙은(min heap) 부모가 자식보다 값이 작아야 하며 최대 힙은 (max heap) 그 반대입니다. 이진트리의 형태를 띄고있어 루트 노드를 1번 정점이라고 한다면, 자식 노드는 각각 2, 3 번 노드가 됩니다. 여기서 알 수 있는건 부모 정점의 번호가 n이라면 왼쪽 자식의 번호는 2*n, 오른쪽 자식의 번호는 2*n + 1 의 규칙을 띄고있습니다. 노드 번호를 배열의 인덱스로 한다면 아래와 같이 1차원 배열로 .. 2021. 6. 3. 이전 1 다음
