연습문제 2-5(5) min heap

문제 설명

이진 힙은 항상 부모 노드가 가지는 값이 자식 노드가 가지는 값보다 크거나 (max heap) 혹은 작거나 같다는 (min heap) 조건을 만족하는 완전 이진 트리(Complete binary tree) 형태의 자료구조이비다.

완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽에서부터 순서대로 나열되는 이진 트리를 말합니다.

이러한 이진 힙은 보통 배열을 통해서 구현하게 됩니다.

배열의 0번 인덱스는 사용하지 않고, 배열의 1번 인덱스에 루트 노드의 값을 저장합니다.

현재 노드의 인덱스가 i일 때, i*2 인덱스에 왼쪽 자식 노드, i*2+1 인덱스에 오른쪽 자식 노드를 저장합니다.

예를 들어 {0, 5, 10, 15}는 루트 노드의 값이 5이고, 루트 노드의 왼쪽 자식과 오른쪽 자식이 각각 10, 15인 이진 힙으로 볼 수 있습니다.

예를 든 이진 힙은 아래와 같은 구조로 표현할 수 있습니다.

배열 arr가 주어졌을 때, 이 배열이 min heap인지 아닌지 판단하여, "YES" 또는 "NO"로 출력하는 프로그램을 구현하세요.

---

입력 형식

· arr : 완전 이진 트리에 담긴 정수 배열

---

출력 형식

· 주어진 arr가 min heap에 해당하는지 여부를 문자열로 반환

---

제약 사항

· 1 <= arr.length <= 100

---

입출력 예시

· 예시1

  · 입력

      · arr = {0, 5, 10, 15}

  · 출력 : "YES"

  · 설명 : 본문의 예시와 같다.

 

· 예시2

  · 입력

      · arr = {0, 20, 22, 17}

  · 출력 : "NO"

  · 설명 : 17은 20의 자식 노드이지만 값이 더 크므로, min heap이 아니다.

---

작성 코드

class Solution255 {
    public String solution(int[] arr) {
    int n = arr.length;
    /*
    i가 1부터 시작하는 이유는 배열의 0번 인덱스를 사용하지 않고,
    1번 인덱스부터 루트 노드의 위치가 시작된다는 가정이 있기 때문입니다.
    완전 이진 트리의 특성 상, 마지막 레벨을 제외한 모든 레벨은 완전히 채워져 있기 때문에,
    마지막 레벨의 노드는 왼쪽에서부터 순서대로 채워지며, 항상 왼쪽 자식 노드부터 존재합니다.
    따라서 마지막 레벨의 노드를 비교할 필요가 없고, 반복문은 마지막 레벨의 부모 노드까지만 순회하면 됩니다.
    또한, 완전 이진 트리의 노드 개수를 n이라고 할 때, 마지막 레벨의 노드 개수는 최대 n/2개입니다.
    따라서, 마지막 레벨을 제외한 모든 레벨의 노드를 비교하기 위해서는 n/2까지 반복문을 돌리면 됩니다.
     */
        for (int i = 1; i <= n / 2; i++) {
            if (i * 2 < n && arr[i] > arr[i * 2]) {
                return "NO";
            }
            if (i * 2 + 1 < n && arr[i] > arr[i * 2 + 1]) {
                return "NO";
            }
        }
        return "YES";
    }

    public static void main(String[] args) {
        Solution255 st = new Solution255();
        int[] arr = {0, 5, 10, 15};
        System.out.println(st.solution(arr));
        int[] arr2 = {0, 20, 22, 17};
        System.out.println(st.solution(arr2));
    }
}

 

정답 코드

class Solution {
    public String solution(int[] arr) {
        boolean isHeap = true;
        int N = arr.length;

        for (int i = 1; i < N; i++) {
            if (2 * i < N && arr[i] > arr[2 * i]) {
                isHeap = false;
                break;
            }
            if (2 * i + 1 < N && arr[i] > arr[2 * i + 1]) {
                isHeap = false;
                break;
            }
        }

        return isHeap ? "YES" : "NO";
    }

    public static void main(String[] args) {
        Solution st = new Solution();
        int[] arr = {0, 5, 10, 15};
        System.out.println(st.solution(arr));
        int[] arr2 = {0, 20, 22, 17};
        System.out.println(st.solution(arr2));
    }
}