2022.09.05 경일 메타버스 23주차 1일 특강 수업내용. 프로젝트 발표, 자료구조와 알고리즘 - 힙(Heap)

프로젝트 발표

• 사용해볼 기능

  • GTTS

  • LOD(Level Of Detail) 기법

• 더 공부해볼 기능

  • 오클루전 컬링

  • 라이팅

  • 네비메쉬

특강 : 힙 (Heap)

• 힙 (Heap) :
  완전 이진 트리에 있는 노드 중에서 값이 가장 큰 노드나 값이 가장 작은 노드를 찾기 위해 만든 자료구조. 우선순위 큐(Priority Queue)라고도 한다.

  • 완전 이진 트리(Complete Binary Tree) :
    마지막 레벨을 제외하고 모든 노드의 차수가 2인 이진 트리

  • 최대 힙(Max Heap) :
    값이 가장 큰 노드를 찾기 위한 힙

  • 최소 힙(Min Heap) :
    값이 가장 작은 노드를 찾기 위한 힙

• 매뉴얼 : https://en.cppreference.com/w/cpp/container/priority_queue

• 힙 정렬 : 힙을 이용한 정렬

• C# .NET 6에서 구현이 되었다 → 유니티는 .NET 4, 따라서 구현이 되어있지 않다.
  ⇒ 사용하려면 스스로 구현해야 한다!

힙의 불변성

• 힙이 되기 위한 조건

  1. 최대 / 최소 원소에 즉각적으로 접근이 가능해야 한다.

     • 그래서 최대 / 최소 원소는 항상 루트 노드에 존재한다.

  2. 부모 노드가 자식 노드보다 항상 크거나(Max Heap), 작아야 한다(Min Heap).

     • 이진 검색 트리와 다르니 헷갈리면 안된다
       ⇒ 이진 검색 트리는 왼쪽이 오른쪽보다 작아야 한다.

연산

• 검색 및 읽기

  • 최대 / 최소 원소에 대해서만 가능하며 O(1)이다.

• 삽입

  • 완전 이진 트리이기 때문에 O(logN)이다.

• 삭제

  • 최대 / 최소 원소에 대해서만 가능하며 O(logN)이다.